Vehicle Routing Problem in logistics: A Genetic Algorithm-based comparative study

Date

2011

Authors

Syed, Ishtiaq Mohammed

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.

Description

This item is available only to currently enrolled UTSA students, faculty or staff. To download, navigate to Log In in the top right-hand corner of this screen, then select Log in with my UTSA ID.

Keywords

Citation

Department

Mechanical Engineering