Parallel solver for vehicle routing and pickup and delivery problems with time windows based on agent negotiation

摘要

In this paper we present a parallel solver for the vehicle routing problem with time windows (VRPTW) and the pickup and delivery problem with time windows (PDPTW). The solver is based on parallel competition of particular solvers solving the given problem instance. The particular solvers are based on negotiation between a fleet of agents representing individual vehicles using a cost structure corresponding to the wellknown travel time savings insertion heuristic. The performance of the solver is assessed on the Homberger-Gehring and Li-Lim benchmark sets for the VRPTW and PDPTW case respectively. While both sets are widely used across the routing community, they were not addressed by previous agent-based studies. Thus the achieved average solution quality of 95% and 87% for the VRPTW and PDPTW cases represents a new best known result for these benchmark sets for agent-based approaches. An analysis of the solver's convergence, runtime and parameter sensitivity is provided within the experimental evaluation section, that has also not been provided by previous agent-based studies.