An Efficient Adaptable Exact Solution Framework for the Capacitated Multi-Trip Vehicle Routing Problem with Time Windows and Its Variants
Abstract: In this paper, we consider the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW), where vehicles are allowed to make multiple trips instead of just one as in the well-known capacitated vehicle routing problem with time windows (CVRPTW). The ability to perform multiple trips is favorable in real-world applications since it reduces the number of vehicles and drivers needed, thus, the operating costs for carriers. Nevertheless, CMTVRPTW is substantially more challenging to solve than the CVRPTW. To the best of our knowledge, all state-of-the-art exact methods struggle in solving Solomon instances with 50 customers. By contrast, our proposed efficient adaptable exact solution framework (EAESF) significantly outperforms all existing exact methods, which can solve All test instances with up to 70 customers to optimality and obtain a near-optimal solution with an average optimality gap less than 0.3% within a 3-hour time limit when there are 80 to 100 customers. The EAESF can be easily adapted to solve four CMTVRPTW variants and achieve exceptional performance. A linkable C++ library for reproducing the results in this paper and solving new instances is available at https://github.com/Yu1423/CMTVRPTW.
Keywords: multi-trip vehicle routing, exact methods, column-and-row generation, reduced cost cuts
Category 1: Applications -- OR and Management Sciences (Transportation )
Category 2: Combinatorial Optimization (Branch and Cut Algorithms )
Category 3: Integer Programming ((Mixed) Integer Linear Programming )
Citation: Yu Yang, "An Efficient Adaptable Exact Solution Framework for the Capacitated Multi-Trip Vehicle Routing Problem with Time Windows and Its Variants", 2021.
Entry Submitted: 01/28/2021
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|