Dynamic Bi-Objective Routing of Multiple Vehicles

Routing of multiple vehicles is an important and difficult problem with applications in the logistic domain [1], especially in the area of customer servicing [2]. In postal services, after-sales services, and in business to business delivery or pick up services one or more vehicles have to be efficiently routed towards customers. If customers can request services over time, the problem becomes dynamic: besides a set of fixed customers, new requests can appear at any point in time. Of course, it is desirable that as many customers as possible are serviced while the tour of any vehicle is kept short. However, it is usually infeasible (due to human resources, labor regulations, or other constraints) to service all customer requests. And clearly, the less customers are left unserviced, the longer the tours become. Thus, the problem is inherently multi-objective. Any efficient solution (smallest maximum tour across all vehicles) is a compromise between the desire to service as many customers as possible (e.g.