An evolutionary approach to vehicle routing problem with dynamic time and precedence relationships

摘要

When the postal service, the bus system, or trucking industry plan for their every day tasks of delivery goods or providing basic transportation needs to people, they are attempting to solve the vehicle routing problem (VRP). However, this can be a daunting task because the VRP is NP-Complete. In this paper, we will address two areas of the VRP that have been relatively unexplored by previous research, yet play an important part in real world applications of the VRP as well as define and create a genetic algorithm (GA) based on these ideas. The first area that we will address deals with the lack of real world data sets, when calculating the times between customers. This new implementation will allow the algorithm to calculate the actual time between customers at a given time of day; thus providing a final solution that is closer to a true optimal set of routes. The second addition to the VRP model will be contributed in the area of precedence relationships. These relationships often exist in real world applications and are necessary in order to help the algorithm to establish routes that are desired by the customers.