The multi-period and multi-depot dynamic vehicle routing problem with time windows

摘要

In this paper, we describe a specific variant of dynamic vehicle routing problem (DVRP) - where the goal is to maximize the number of serviced customers with less cost. Two types of customers are served in this problem: the obligatory customers with time windows and the optional ones without time window. To solve this problem, we propose a method with three steps. The first step is to construct a skeleton of obligatory customers by respecting their time windows. In the second step, optional customers will be inserted to complete the route. The third step is to adapt to the dynamic information by managing a set of plan. We prove the feasibility of this approach by experiments.