TY - JOUR
T1 - Exact and heuristic solution of the consistent vehicle-routing problem
AU - Goeke, Dominik
AU - Roberti, Roberto
AU - Schneider, Michael
PY - 2019/7
Y1 - 2019/7
N2 - Providing consistent service by satisfying customer demands with the same driver (driver consistency) at approximately the same time (arrival-time consistency) allows companies in last-mile distribution to stand out among competitors. The consistent vehicle-routing problem (ConVRP) is a multiday problem addressing such consistency requirements along with traditional constraints on vehicle capacity and route duration. The literature offers several heuristics but no exact method for this problem. The state-of-the-art exact technique to solve VRPs-column generation (CG) applied to route-based formulations in which columns are generated via dynamic programming-cannot be successfully extended to the ConVRP because the linear relaxation of route-based formulations is weak. We propose the first exact method for the ConVRP, which can solve medium-sized instances with five days and 30 customers. The method solves, via CG, a formulation in which each variable represents the set of routes assigned to a vehicle over the planning horizon. As an upper bounding procedure, we develop a large neighborhood search (LNS) featuring a repair procedure specifically designed to improve the arrival-time consistency of solutions. Used as stand-alone heuristic, the LNS is able to significantly improve the solution quality on benchmark instances from the literature compared with state-of-the-art heuristics.
AB - Providing consistent service by satisfying customer demands with the same driver (driver consistency) at approximately the same time (arrival-time consistency) allows companies in last-mile distribution to stand out among competitors. The consistent vehicle-routing problem (ConVRP) is a multiday problem addressing such consistency requirements along with traditional constraints on vehicle capacity and route duration. The literature offers several heuristics but no exact method for this problem. The state-of-the-art exact technique to solve VRPs-column generation (CG) applied to route-based formulations in which columns are generated via dynamic programming-cannot be successfully extended to the ConVRP because the linear relaxation of route-based formulations is weak. We propose the first exact method for the ConVRP, which can solve medium-sized instances with five days and 30 customers. The method solves, via CG, a formulation in which each variable represents the set of routes assigned to a vehicle over the planning horizon. As an upper bounding procedure, we develop a large neighborhood search (LNS) featuring a repair procedure specifically designed to improve the arrival-time consistency of solutions. Used as stand-alone heuristic, the LNS is able to significantly improve the solution quality on benchmark instances from the literature compared with state-of-the-art heuristics.
KW - Column generation
KW - Consistent vehicle routing problems
KW - Customer service
KW - Large neighborhood search
UR - http://www.scopus.com/inward/record.url?scp=85071943413&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071943413&partnerID=8YFLogxK
U2 - 10.1287/trsc.2018.0864
DO - 10.1287/trsc.2018.0864
M3 - Article
AN - SCOPUS:85071943413
VL - 53
SP - 1023
EP - 1042
JO - Transportation Science
JF - Transportation Science
SN - 0041-1655
IS - 4
ER -