Two-Stage Algorithm For Green Vehicle Routing Problem With Time Window

Abstract

In the Vehicle routing problem with time windows (VRPTW), vehicle must be designed to satisfy the demand of each location, under capacity, time window, and precedence constraints. To satisfy the requirements of customers, constraints focus on time window and load of vehicles. In this study, a Green VRPTW model is proposed considering the coefficient of ��2 equivalent emission from the total distance travelled by vehicles along their network as an additional factor then integrate it into a separate kind of cost function – emission cost - in the optimization model. The model aims to find an optimally routed transportation network so that the sum of travel distance cost and emission cost is minimized. As the problem is an NP-hard problem, the Two-stage approach is proposed with a pre-clustered stage to divide the initial problem into subproblems using K-means clustering algorithm. Solomon's VRPTW benchmark problems published from 1992 is taken as the dataset applied in this GVRPTW problem to validate the proposed method, then the results and computation time is compared with the results in LP model. After the comparison and analysis, data sets C1 is proved to be the most suitable one for this GVRPTW.