The Multi-Trip Vehicle Routing Problem (MTVRP) is an extension of the Capacitated Vehicle Routing Problem (CVRP) where each vehicle is allowed to perform more routes during its working period. A route is a simple circuit visiting the depot and some customers and such that the total request of the customers served does not exceed the vehicle capacity. The cost (working time) of a route is defined as the sum of the travel costs (travel times) of the edges traversed. A schedule for a vehicle is a subset of routes having total working time not exceeding a maximum time, and visiting each customer at most once. The cost of a schedule is the sum of the costs of its routes. The objective of the MTVRP is to design a set of schedules of minimum total cost such that all customers are visited exactly once. In this work, we present two exact methods for the MTVRP using two different formulations. The computational results show that instances with up to 100 customers can be consistently solved to optimality.

Exact Methods for the Multi-Trip Vehicle Routing Problem

MINGOZZI, ARISTIDE;TOTH, PAOLO
2010

Abstract

The Multi-Trip Vehicle Routing Problem (MTVRP) is an extension of the Capacitated Vehicle Routing Problem (CVRP) where each vehicle is allowed to perform more routes during its working period. A route is a simple circuit visiting the depot and some customers and such that the total request of the customers served does not exceed the vehicle capacity. The cost (working time) of a route is defined as the sum of the travel costs (travel times) of the edges traversed. A schedule for a vehicle is a subset of routes having total working time not exceeding a maximum time, and visiting each customer at most once. The cost of a schedule is the sum of the costs of its routes. The objective of the MTVRP is to design a set of schedules of minimum total cost such that all customers are visited exactly once. In this work, we present two exact methods for the MTVRP using two different formulations. The computational results show that instances with up to 100 customers can be consistently solved to optimality.
Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 7)
757
759
A. Mingozzi; R. Roberti; P. Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/100064
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact