Conflict-Free Vehicle Routing Problems (CF-VRPs) arise in manufacturing, transportation and logistics facilities where Automated Guided Vehicles (AGVs) are utilized to move loads. Unlike \textit{Vehicle Routing Problems} arising in distribution management, CF-VRPs explicitly consider the limited capacity of the arcs of the guide path network to avoid collisions among vehicles. AGV applications have two peculiar features. First, the uncertainty affecting both travel times and machine ready times may result in vehicle delays or anticipations with respect to the fleet nominal plan. Second, the relatively high vehicle speed (in the order of one or two meters per second) requires vehicle plans to be revised in a very short amount of time (usually few milliseconds) in order to avoid collisions. In this paper we present fast exact algorithms to recover plan feasibility in real-time. In particular, we identify two corrective actions that can be implemented in real-time and formulate the problem as a linear program with the aim to optimize four common performance measures (total vehicle delay, total weighted delay, maximum route duration and total lateness). Moreover, we develop tailored algorithms which, tested on randomly generated instances of various sizes, prove to be three orders of magnitude faster than using off-the-shelf solvers.

Recovering feasibility in real-time conflict-free vehicle routing

Abstract

Conflict-Free Vehicle Routing Problems (CF-VRPs) arise in manufacturing, transportation and logistics facilities where Automated Guided Vehicles (AGVs) are utilized to move loads. Unlike \textit{Vehicle Routing Problems} arising in distribution management, CF-VRPs explicitly consider the limited capacity of the arcs of the guide path network to avoid collisions among vehicles. AGV applications have two peculiar features. First, the uncertainty affecting both travel times and machine ready times may result in vehicle delays or anticipations with respect to the fleet nominal plan. Second, the relatively high vehicle speed (in the order of one or two meters per second) requires vehicle plans to be revised in a very short amount of time (usually few milliseconds) in order to avoid collisions. In this paper we present fast exact algorithms to recover plan feasibility in real-time. In particular, we identify two corrective actions that can be implemented in real-time and formulate the problem as a linear program with the aim to optimize four common performance measures (total vehicle delay, total weighted delay, maximum route duration and total lateness). Moreover, we develop tailored algorithms which, tested on randomly generated instances of various sizes, prove to be three orders of magnitude faster than using off-the-shelf solvers.
Scheda breve Scheda completa Scheda completa (DC)
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: https://hdl.handle.net/11587/475128
Attenzione

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

• ND
• ND
• ND