Scientific Program > Talks by Speaker > Uhm Hyunseop

The multi-depot vehicle routing problem is considered with the constraint that vehicles may travel with at least certain distance separation from each other for the safety purpose. This kind of instance can be found in the multi drone operation for delivery or the vehicles operation for hazardous material transportation. It is assumed that safety can be achieved if the vehicles travel apart at any time with at least safety distance predetermined. Vehicles may visit customers for service which are distributed on the two dimensional space with Euclidean distance. Customers have their own demand and vehicle may visit customers whose total demands are within the vehicle's capacity. Vehicles may travel with same speed, i.e., traveling time is proportional to the distance, and may not stop during the trip until returning to the depot, but may delay the departure from the depot for the purpose of the safety distance separation on the trip. The objective is to find the vehicle's traveling routes with the minimal total time to complete customer's demand under the safety distance separation. Mathematical formulation is suggested with the mixed integer linear programming. Meta-heuristics of tabu search algorithm is also suggested with the 2-opt procedure. The performance of the suggested algorithm is evaluated for the randomly generated instances and compared with optimal solutions by the mixed integer programming for small size instances. Computational experiment shows that it can be applied to the practical cases with the reasonable computation time.