Adapting research methods for solving the VRPTW to real life problems

Abstract

In this paper we present the evolution of the research method called ALADIN to be implemented in real life situations. In the first section of the paper we present the algorithm ALADIN, based on a combination of insertions, additions and other simple procedures to construct the routes for the VRPTW. In the second section of the paper we discuss the main differences between the benchmark problems and daily situations on transport companies.

The main problem arises from the fact that real distances and times must be considered instead of Euclidean distances. Therefore two different modifications must be implemented, first the calculation of distances, that will provide the total distance travelled by the vehicles. Depending on the length of this distance, a higher cost might arise. Second, the times needed to travel from one point to another, and that must be considered for the time window constraints. These times might vary from day to day, and depend mainly on the time of the day in which the vehicle drives. It may also vary depending on the season of the year, weather conditions, and so on.

In the third section we present the modifications implemented in the original method to adapt it to real life situations, and last, we present a real case study, which has been solved by implementing other commercial software.