A Branch and Price Algorithm for the Heterogeneous Fleet Multi-Depot Multi-Trip Vehicle Routing Problem with Time Windows
Munise Kübra Şahin () and
Hande Yaman ()
Additional contact information
Munise Kübra Şahin: Research Centre for Operations Research and Statistics, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium
Hande Yaman: Research Centre for Operations Research and Statistics, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium
Transportation Science, 2022, vol. 56, issue 6, 1636-1657
Abstract:
The multi-trip vehicle routing problem (MTVRP) extends the well-known VRP by allowing vehicles to perform several trips in a workday. The motivation arises from the new challenges in city logistics that push companies to use smaller and cleaner vehicles such as cargo bikes. With the integration of small vehicles into the fleet, many companies start to operate with a heterogeneous fleet and use multiple depots located in the city centers to reload the small vehicles. Inspired by these new challenges the companies face, we study the heterogeneous fleet multi-depot MTVRP with time windows under shared depot resources where small and large vehicles have different travel times in certain areas. We formulate this problem using workday variables and propose a branch and price algorithm that exhibits an enhanced performance by a new heuristic algorithm based on the reduction in the graph size. The proposed algorithm introduces a new way to compute the completion bounds using the iterative structure of the state-space augmenting algorithm and eliminates the need for solving a separate relaxation. We conduct experiments on modified small- and medium-size instances from Solomon’s benchmark set. The results of our computational experiments show that the proposed algorithm is very effective and can solve instances with up to 40 customers, three depots, and two types of vehicles.
Keywords: multi-trip vehicle routing; multi-depot vehicle routing; heterogeneous fleet; time windows; branch and price (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1146 (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:56:y:2022:i:6:p:1636-1657
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().