Skip to Main content Skip to Navigation
New interface
Conference papers

An Exact Method to Solve the Multi-Trip Vehicle Routing Problem with Multi Time Windows

Abstract : This article tackles the multi-trip vehicule routing problem with time windows and limited du-ration. A trip is a timed route such that a succession of trips can be assigned to one vehicle. We provide a two-phase exact algorithm to solve it. The rst phase enumerates possible ordered lists of client matching trip maximum duration criterion. The second phase uses a Branch and Price scheme to generate and choose best set of trips to visit all customers. We propose a set covering formulation as the column generation master problem, where columns (variables) rep-resent trips. The sub-problem selects appropriate timing for trips and has a pseudo-polynomial complexity. Computional results on Solomon's benchmarks are presented. The computional times obtained with our new algorithm are much lower than the ones obtained in the sole exact algorithm previously published on this problem
Document type :
Conference papers
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rodolphe Giroudeau Connect in order to contact the contributor
Submitted on : Friday, November 13, 2020 - 12:44:26 PM
Last modification on : Thursday, September 29, 2022 - 5:01:41 AM
Long-term archiving on: : Sunday, February 14, 2021 - 6:49:16 PM


Files produced by the author(s)


  • HAL Id : lirmm-00702137, version 1
  • IRSTEA : PUB00037859


Rodolphe Giroudeau, Florent Hernandez, Olivier Naud, Frédéric Semet. An Exact Method to Solve the Multi-Trip Vehicle Routing Problem with Multi Time Windows. 5th International Workshop on Freight Transportation and Logistics (ODYSSEUS), May 2012, Mykonos Island, Greece. pp.9-12. ⟨lirmm-00702137⟩



Record views


Files downloads