Solving the Vehicle Routing Problem with Practical Considerations

Chung-Cheng Lu*, Cheng-Yu Chang


研究成果: Conference contribution同行評審


Purpose of this paper:
This study deals with a generalization of the classical vehicle routing problem with time windows (VRPTWs). The problem aims to determine the optimal routes for a fleet of homogeneous vehicles deployed in a depot of a city logistics service provider (CLSP) that services a set of customers, including general customers and enterprise customers. In addition to the constraints of the VRPTW, three practical considerations for the CLSP, namely, service capacity of sales drivers, delivery time preference of customers, and fairness of drivers’ performance bonus are explicitly addressed in this problem.

A two-stage optimization model-based approach is developed to deal with the practical generalization of the VRPTW. This solution approach adopts the concept of "cluster-first-routesecond". The first stage solves a clustering model that divides the set of customers into a given number of clusters, each of which is serviced by a vehicle (or a sales driver). The objective of the clustering model is to minimize the total distance and the maximal performance bonus of the drivers. The service capacity of SDs and the fairness of their performance bonus are taken into account in the clustering model. In the second stage, a routing model is solved to generate the route for servicing each cluster of customers, determined by the clustering model. The objective of the routing model is to minimize the total cost including the traveling cost and the penalty for violating the preferred delivery times of general customers.

To examine the performance of the proposed model, this study generates a number of test instances based on the historical data provided by a large CLSP in Taiwan and solves the test instances using Gurobi. The results show that the proposed approach is able to effectively obtain the vehicle routes which address the aforementioned practical concerns for the CLSP.

The major contribution of this paper is on proposing an efficient approach to deal with the practical generalization of the VRPTW, which greatly facilitate the CLSP effectively planning vehicle routes to service its customers.
主出版物標題International Symposium on Logistics (ISL2018)
出版狀態Published - 7月 2018
事件International Symposium on Logistics (ISL2018) - Bali, Indonesia
持續時間: 8 7月 201811 7月 2018


ConferenceInternational Symposium on Logistics (ISL2018)


深入研究「Solving the Vehicle Routing Problem with Practical Considerations」主題。共同形成了獨特的指紋。