Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs

Qie He (), Stefan Irnich () and Yongjia Song ()
Additional contact information
Qie He: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455;
Stefan Irnich: Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, 55128 Mainz, Germany;
Yongjia Song: Department of Industrial Engineering, Clemson University, Clemson, South Carolina 29634

Transportation Science, 2019, vol. 53, issue 5, 1409-1426

Abstract: Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a network of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation and customers’ inconvenience costs. In this paper, we introduce the vehicle routing problem with time windows and convex node costs (VRPTW-CNC), in which we model each customer’s inconvenience cost as a convex function of the service start time at that customer. The VRPTW-CNC combines and extends both the standard vehicle routing problem with time windows and some previous results on the optimal service scheduling problem over a fixed route. We propose a branch-and-cut-and-price algorithm to solve the VRPTW-CNC with general convex inconvenience cost functions. To solve the pricing problem, our labeling algorithm only generates labels that possibly lead to optimal schedule times over a route, which significantly improves the effectiveness of pricing. Extensive computational results demonstrate the effectiveness of our approach.

Keywords: vehicle routing problem; branch-and-cut-and-price; labeling algorithm; convex node costs; integrated routing and scheduling (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0891 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:5:p:1409-1426

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().