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: View citations in EconPapers (2)

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 ().