-

 

 

 




Optimization Online





 

An Efficient Adaptable Exact Solution Framework for the Capacitated Multi-Trip Vehicle Routing Problem with Time Windows and Its Variants

Yu Yang(yu.yang***at***ise.ufl.edu)

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.

Download: [PDF]

Entry Submitted: 01/28/2021
Entry Accepted: 01/29/2021
Entry Last Modified: 01/28/2021

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society