Solving the Vehicle Routing Problem with Practical Considerations

Chung-Cheng Lu*, Cheng-Yu Chang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageEnglish
Title of host publicationInternational Symposium on Logistics (ISL2018)
Number of pages1
StatePublished - Jul 2018
EventInternational Symposium on Logistics (ISL2018) - Bali, Indonesia
Duration: 8 Jul 201811 Jul 2018


ConferenceInternational Symposium on Logistics (ISL2018)


Dive into the research topics of 'Solving the Vehicle Routing Problem with Practical Considerations'. Together they form a unique fingerprint.

Cite this