We investigate a vehicle routing problem in which customer requests are either known in advance with respect to the planning of the distribution, or they arrive online during the distribution process. Each request is associated with a time window. The company managing the distribution has a given fleet of vehicles to serve the customers, and, in addition, occasional drivers are available to perform the service, i.e., private citizens who are willing to distribute some customer orders in exchange for a compensation. Each occasional driver specifies the time window in which he/she is available. A penalty is incurred when violating time windows as well as when a request is not served. The objective of the company is to determine the distribution plan that minimises the distribution cost, which is given by the sum of the cost of regular vehicles, the compensation paid to the occasional drivers and the penalty cost. In addition, we design and implement a solution method which is based on an insertion algorithm evaluating each request singularly. Albeit being simple, this approach allows to handle dynamic requests and to adjust the distribution plan in real-time. Then, we propose a re-optimisation approach in which the solution constructed through the insertion algorithm is periodically passed to a variable neighborhood search algorithm. In a detailed computational study, we analyse the behavior of the proposed solution approaches. In addition, we evaluate the impact of dynamic information through a comparison of online approaches with an a priori information scenario.

The online vehicle routing problem with occasional drivers

Guerriero F.
;
Macrina G.
2021

Abstract

We investigate a vehicle routing problem in which customer requests are either known in advance with respect to the planning of the distribution, or they arrive online during the distribution process. Each request is associated with a time window. The company managing the distribution has a given fleet of vehicles to serve the customers, and, in addition, occasional drivers are available to perform the service, i.e., private citizens who are willing to distribute some customer orders in exchange for a compensation. Each occasional driver specifies the time window in which he/she is available. A penalty is incurred when violating time windows as well as when a request is not served. The objective of the company is to determine the distribution plan that minimises the distribution cost, which is given by the sum of the cost of regular vehicles, the compensation paid to the occasional drivers and the penalty cost. In addition, we design and implement a solution method which is based on an insertion algorithm evaluating each request singularly. Albeit being simple, this approach allows to handle dynamic requests and to adjust the distribution plan in real-time. Then, we propose a re-optimisation approach in which the solution constructed through the insertion algorithm is periodically passed to a variable neighborhood search algorithm. In a detailed computational study, we analyse the behavior of the proposed solution approaches. In addition, we evaluate the impact of dynamic information through a comparison of online approaches with an a priori information scenario.
Crowd-shipping
Logistics
Occasional drivers
Online vehicle routing
Re-optimisation
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/20.500.11770/311198
 Attenzione

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

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