Title :

A Branch&Cut algorithm for the Multi-Trip Vehicle Routing Problem with Time Windows

Author(s) :

Cattaruzza, Diego [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Gianessi, Paolo [Auteur]
Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes [LIMOS]
École des Mines de Saint-Étienne [Mines Saint-Étienne MSE]

Conference title :

VeRoLog 2016: annual workshop of the EURO working group on Vehicle Routing and Logistics optimization (VeRoLog)

City :

Nantes

Country :

France

Start date of the conference :

2016-06-06

HAL domain(s) :

Informatique [cs]/Modélisation et simulation

English abstract : [en]

The Multi-trip Vehicle Routing Problem with Time Windows (MTVRPTW) generalizes the well-known Capacitated Vehicle Routing Problem (CVRP) in that vehicles can recharge at the depot and perform more than one trip within a ...
Show more >The Multi-trip Vehicle Routing Problem with Time Windows (MTVRPTW) generalizes the well-known Capacitated Vehicle Routing Problem (CVRP) in that vehicles can recharge at the depot and perform more than one trip within a maximum shift length but must comply customer time windows. In its most frequent form, which we address, the MTVRPTW features service-dependent loading times, i.e. the time to recharge depends on the total service time of the subsequent trip. Other variants exist that consider e.g. profits or trips with limited duration.As far as we are aware of, the literature of exact methods for the MTVRPTW is still scarce. We propose a three-index MILP formulation for the MTVRPTW that makes use of base and replenishment arcs. The former model the direct connection between two nodes, while the latter imply a recharge in between two clients. Base and replenishment arc variables are vehicle-indexed. Replenishment arcs allow to represent a journey as an elementary path and thus to ensure connectivity by separating SECs on a transformation of the graph. Further sets of two-indexed variables allow to impose time windows, shift length, and service-dependent loading time constraints. The use of classical capacity constraints to enforce the load limit on vehicles leads to a Branch&Cut algorithm. Capacity constraints are then strengthened after branching decisions to exploit some properties of the vehicle index.Preliminary tests have been conducted, with promising results.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL