| The Vehicle Routing Problem (VRP) with Simultaneous Delivery and Pick-up (VRP/SDP) with Time Windows (VRP/SDP/TW) is a variant of the classical vehicle routing problem where customers require simultaneous delivery and pick-up at their locations to be completed within a time windows. The objective in VRP/SDP/TW is to assign a number of vehicles to routes that connect customers and depot such that the overall distance travelled is minimized and the delivery and pick-up operations are completed within the time windows requested by the customers.;A Genetic Algorithm (GA) is applied to the VRP/SDP and VRP/SDP/TW problems. Three GA models, namely Random (R), Nearest Neighbor (NN) (Shi, Zhao, and Gong, 2009), and Greedy Randomized Adaptive Search Procedure (GRASP) (Vural, 2007), are adopted to develop three variations of GA as GA/R, GA/NN, and GA/GRASP. In Phase 1, the three GA models are benchmarked against the models in the literature. In Phase 2, the three GA models are benchmarked against each other using a hypothetical data set for a variety of problem sizes. Both phases in this comparative study use overall routing distance and computational time as the performance metrics for the VRP/SDP and VRP/SDP/TW problems.;The results in Phase 1 show that GA/GRASP typically outperforms the other models for the VRP/SDP problem. However, all three models exhibit the same performance for the VRP/SDP/TW problem when the data in the literature is used. Phase 1 indicates that the potential strength of the initialization algorithms is not visible for the data sets used in the literature. Phase 2 uses a variety of problem sizes based on hypothetical data for in-depth comparison. In this case, GA/GRASP outperforms both GA/R and GA/NN for all sizes of VRP/SDP and VRP/SDP/TW problems. For the same data set, GA/NN outperforms GA/R. |
