An Exact Algorithm for the Multitrip Vehicle Routing Problem

Aristide Mingozzi, Roberto Roberti, Paolo Toth

Research output: Contribution to journalJournal articleResearchpeer-review

748 Downloads (Pure)

Abstract

The multitrip vehicle routing problem (MTVRP) is a variant of the capacitated vehicle routing problem where each vehicle can perform a subset of routes, called a vehicle schedule, subject to maximum driving time constraints. Despite its practical importance, the MTVRP has received little attention in the literature. Few heuristics have been proposed, and only an exact algorithm has been presented for a variant of the MTVRP with customer time window constraints and unlimited driving time for each vehicle. We describe two set-partitioning-like formulations of the MTVRP. The first formulation requires the generation of all feasible routes, whereas the second formulation is based on the generation of all feasible schedules. We study valid lower bounds, based on the linear relaxations of both formulations enforced with valid inequalities, that are embedded into an exact solution method. The computational results show that the proposed exact algorithm can solve MTVRP instances taken from the literature, with up to 120 customers.
Original languageEnglish
JournalI N F O R M S Journal on Computing
Volume25
Issue number2
Pages (from-to)193-207
Number of pages15
ISSN1091-9856
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • COMPUTER
  • OPERATIONS
  • TABU SEARCH ALGORITHM
  • TIME WINDOWS
  • STRATEGIES
  • TRIPS
  • vehicle routing
  • multiple trips
  • dual ascent heuristics
  • column-and-cut generation
  • Algorithms
  • Routing algorithms
  • Vehicle routing
  • Network routing
  • Capacitated vehicle routing problem
  • Column-and-cut generation
  • Computational results
  • Dual ascent heuristics
  • Multiple trips
  • Practical importance
  • Time window constraint
  • Vehicle Routing Problems
  • HEURISTIC algorithms

Fingerprint Dive into the research topics of 'An Exact Algorithm for the Multitrip Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this