Program > By author > Adamo Tommaso

This article deals with the Speed Optimization Problem (SOP) for the Pickup and Delivery Routing Problem under Track Contention, a particular vehicle routing problem in which loads have to be transported between origin-destination pairs by means of vehicles traveling along a capacitated network. The aim is to find for each vehicle a conflict-free routing and to determine the corresponding travel speeds, in order to minimize the total energy consumption.

These problems arise in at least three different contexts that we are aware of. The first is the movement of Automated Guided Vehicles in Material Handling Systems, particularly those using batteries. A second application context is the routing of Unmanned Aerial Vehicle in controlled airspace. Finally, the problem might arise in scheduling and routing of trains where a given track might only be occupied by a single train due to safety considerations.

In this article, we propose a Branch-And-Bound algorithm for the problem, based on the relaxation obtained by removing track-contention constraints. In particular, the resulting relaxed problem is nonlinear and separable, and its optimal solution can be determined by solving in quadratic time a SOP for each vehicle. We devise a feasibility-check procedure aiming to determine if the optimal solution of the relaxation problem corresponds to a conflict-free routing. Finally, the branching procedure applies space-based and time-based branching constraints, so that to cut off conflicts detected by the feasibility-check procedure. We demonstrate the efficiency and applicability of the proposed approach by solving instances of increasing complexity.