Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost

Zhixing Luo (), Hu Qin (), Wenbin Zhu () and Andrew Lim ()
Additional contact information
Zhixing Luo: International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, 210093 Nanjing, China; and Department of Industrial and Systems Engineering, National University of Singapore, Singapore 119260
Hu Qin: School of Management, Huazhong University of Science and Technology, 430074 Wuhan, China
Wenbin Zhu: School of Business Administration, South China University of Technology, 510640 Guangzhou, China
Andrew Lim: Department of Industrial and Systems Engineering, National University of Singapore, Singapore; and International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, 210093 Nanjing, China

Transportation Science, 2017, vol. 51, issue 2, 668-687

Abstract: This paper addresses a new vehicle routing problem that simultaneously involves time windows, split delivery, and linear weight-related cost. This problem is a generalization of the split delivery vehicle routing problem with time windows (SDVRPTW), which consists of determining a set of least-cost vehicle routes to serve all customers while respecting the restrictions of vehicle capacity and time windows. The travel cost per unit distance is a linear function of the vehicle weight and the customer demand can be fulfilled by multiple vehicles. To solve this problem, we propose an exact branch-and-price-and-cut algorithm, where the pricing subproblem is a variant of the resource-constrained elementary shortest path problem. We first prove that at least one optimal solution to the pricing subproblem is associated with an extreme delivery pattern, and then we design a tailored and novel label-setting algorithm to solve the pricing subproblem. Computational results show that our proposed algorithm can handle both the SDVRPTW and our new problem effectively.

Keywords: vehicle routing; time windows; split delivery; linear weight-related cost; branch and price and cut (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/trsc.2015.0666 (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:51:y:2017:i:2:p:668-687

Access Statistics for this article

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