Modeling of a Vehicle Routing Problem with Actual Constraints and Re-scheduling for Dynamic Requests

In this paper, we model the delivery planning problem in a company conducting shipping business as a vehicle routing problem. According to an interview with this company, we formulate the problem based on the vehicle routing problem with time windows (VRPTW) with addition of lunch break constraints and multi-person work constraints. The quality of a routing plan is evaluated by the standard evaluation indices such as the number of vehicles and total operating time of the drivers with an optional evaluation index that evaluates the evenness of the operating time between the drivers. We also formulate a dynamic scheduling model, which is essential in practical delivery planning systems, to deal with additional orders that occur during delivery. We create a problem instance for the modeled problem that imitates the real situation in the company using actual map data, where the traveling time and distance between any two points is acquired from the digital map provided by ZENRIN co., ltd. In order to solve the problem instance we created, we propose a solution method based on both tabu search and iterated local search. In the experiment, we optimized this problem instance using the proposed method and evaluate the validity of the modeling.