A Decision Model Based on a GRASP Genetic Algorithm for Solving the Vehicle Routing Problem

A Decision Model Based on a GRASP Genetic Algorithm for Solving the Vehicle Routing Problem

Hiba Yahyaoui (ISG, Tunis, Tunisia), Saoussen Krichen (ISG, Tunis, Tunisia) and Abdelkader Dekdouk (Dhofar University, Salalah, Oman)
Copyright: © 2018 |Pages: 19
DOI: 10.4018/IJAMC.2018040104

Abstract

In this paper, the authors address a delivery process with time requirements in the supply chain, stated as follows: orders launched from customers are centralized and assigned to firms' depots for the delivery process. The consideration of a depot and a set of customers belonging to different firms, is seen as a VRPTW that serves n customers using a subset of vehicles. Implemented in this article is a DSS that handles the delivering activity in the supply chain. The DSS embeds a Greedy Randomized Adaptive Search Procedure (GRASP) and Genetic components for generating promising solutions in a concurrently run time. Simulation results are conducted on Solomon's benchmarks. The DSS records very competitive results regarding state-of-the-art approaches.
Article Preview

1. Introduction

We propose in this paper a new platform that handles the delivery process in the supply chain while using homogeneous trucks. A set of cost saving pathways is the output in order to deliver already ordered items. This problem belongs to the class of vehicle routing problems (VRPs) that have a fundamental economic importance in the field of distribution within the supply chain. The main objective of the VRP is to deliver a set of customers with known demands while minimizing the transportation costs and respecting the delivery time expected by the customer. Hence, the VRP consists in finding a set of routes for k identical vehicles based at the distribution center, such that each route is visited once. By involving additional constraints and requirements on routes construction, various VRP variants are be defined. The capacitated VRP (CVRP) is the most addressed version that involves a fleet of vehicles specified by a weight capacity. The VRP with Time Windows (VRPTW) imposes a prefixed threshold of delivery time that should not be exceed in order to satisfy customers’ demands. The VRP with pick-up and delivery (PDP) generalizes the basic VRP in the sense that specific quantities of goods are to be picked up and delivered from intermediate customers. Alternatively, the heterogeneous fleet VRP (HVRP) offers the opportunity of considering different capacities in the set of vehicles.

The existing solution approaches for the VRPTW deal with single-solution-based meta-heuristics such as large neighborhood approaches (Prescott‐Gagnon, Desaulniers & Rousseau, 2009)., 2007), iterated local searches (Ibaraki et al., 2008; Miranda & Conceicao, 2016), and multi-start local searches (Lim & Zhang, 2007) and population-based metaheuristics.

The evolutionary strategies confirmed their effectiveness by providing good quality solutions not only on benchmark tests but also in many real-life instances for numerous optimization problems. Hence, we proposed a population-based hybrid metaheuristic that consists of GRASP genetic algorithm (GGA). It proceeds iteratively by improving currently processed populations by the use of genetic operators and a continuous vector evaluation of the generated solutions with respect to the traveled distance and the number of used vehicles. Our method is compared to four recent and potential state-of-the-art approaches. The Agent-Based Cooperative Population Learning Algorithm (CPLA) (Barbicha, 2014), the Localized Genetic Algorithm (LGA) (Ursani, Essam, Cornforth & Stocker, 2011), a penalty-based memetic algorithm by extending the edge assembly memetic algorithm (EAMA) (Nagata, Brasy & Dullaert, 2010) and a hybrid shuffled frog leaping algorithm (HSFLA) (Luo, Li & Chen, 2015). In CPLA the process is divided into stages, various heuristics are used at each stage and run under the cooperation scheme defined separately for each stage LGA is a scheme designed by applying a genetic algorithm to solve the VRPTW using a localized optimization framework. The EAMA introduces an edge assembly crossover into a memetic algorithm with a penalty function to avoid violations of constraints from offspring solutions generated by the crossover operator. The HSFLA is a hybrid heuristic based on the memetic evolution with a neighborhood search based on the modified and extended extremal optimization.

We state in the subsequent of this paper a specifically designed genetic algorithm embedded into a decision support system. This paper is structured as follows. Section 2 states the problem description and the mathematical formulation followed with an example. Section 3 details the GGA algorithm and its operators specifically adapted to the VRPTW.

Section 4 deals with an extensive computational study on Solomon's benchmarks in order to highlight the efficiently of the GGA in generating effective solutions. This paper is enclosed with a decision support system (DSS) that guides the decision maker (DM) for a fast convergence to the appropriate transport configuration applied to real case study.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing