A Heuristic Approach to the Driver and Vehicle Routing Problem

摘要

This paper presents a heuristic approach for a routing problem with two depots and involving vehicles and drivers. Vehicles must leave from one depot and arrive to the other, while drivers should leave and return to the same depot and their routes can not exceed a given duration. With these conditions, drivers must change vehicles in order to go back to their base depots. These changes can only take place at some particular nodes known as exchange locations. The heuristic approach in this paper is a two-phase method for the problem with one exchange location. In the first phase it solves a mathematical model to obtain drivers' routes. In the second phase it builds vehicles' routes over the given drivers' routes. Computational results show that the proposed approach can find high quality solutions for instances with up to 50 nodes.