A New Multi-Criteria Solving Procedure for Multi-Depot FSM-VRP with Time Window

A New Multi-Criteria Solving Procedure for Multi-Depot FSM-VRP with Time Window

Lahcene Guezouli (University of Batna 2, Batna, Algeria) and Samir Abdelhamid (University of Batna 2, Batna, Algeria)
Copyright: © 2017 |Pages: 18
DOI: 10.4018/IJAIE.2017010101


One of the most important combinatorial optimization problems is the transport problem, which has been associated with many variants such as the HVRP and dynamic problem. The authors propose in this study a decision support system which aims to optimize the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types (with distinct capacities and costs) and multiple available depots, that the authors call the Multi-Depot HVRPTW by respecting a set of criteria including: schedules requests from clients, the heterogeneous capacity of vehicles..., and the authors solve this problem by proposing a new scheme based on a genetic algorithm heuristics that they will specify later. Computational experiments with the benchmark test instances confirm that their approach produces acceptable quality solutions compared with previous results in similar problems in terms of generated solutions and processing time. Experimental results prove that the method of genetic algorithm heuristics is effective in solving the MDHVRPTW problem and hence has a great potential.
Article Preview

1. Introduction

Within the wide scope of logistics management, transportation plays a central role and is a crucial activity in the delivery of goods and services. The transport problem is one of the mainly essential combinatorial optimization problems that have taken the interest of several researchers. Huge research efforts have been devoted to the study of logistic problems and thousands of papers have been written on many variants of this problem such as Traveling Salesman Problem (TSP) (Toth et al., 2001), Vehicle Routing Problem (VRP) and supply chain management (SCM) (Pisinger et al., 2007).

The VRP (Golden et al., 2007) and (Toth et al., 2001) is one of the most studied combinatorial optimization problems and it consists of the optimal design of routes to be used by a fleet of vehicles to satisfy the demands of customers.

Many other related problems are associated with VRP such as the Heterogeneous Fleet Vehicle Routing Problem (HVRP), which differs from the classical VRP in that it deals with a heterogeneous fleet of vehicles having various capacities and both fixed and variable costs (Xu et al., 2014). Therefore, the HVRP involves designing a set of vehicle routes, each starting and ending at the depot, for a heterogeneous fleet of vehicles which services a set of customers with specific demands. Each customer is visited only once, and the total demand of a route should not exceed the loading capacity of the vehicle assigned to it. The routing cost of a vehicle is the sum of its fixed costs and variable costs incurred proportionately to the travel distance.

The main objective is to minimize the total of such routing costs. The number of available vehicles of each type is assumed to be unlimited and the total sum of the delays.

In the literature, three HVRP versions have been studied. The first one was introduced by (Golden et al., 1984), in which variable costs are uniformly given over all vehicle types with the number of available vehicles assumed to be unlimited for each type. This version is also called the Fleet Size and Mix VRP “FSM” (Ismail et al., 2008). This version that we are consider in this paper.

The second version considers the variable costs, depending on the vehicle type, which is ignored in the first version. This version is referred as HVRP (Gheysens, et al., 1986), the FSM with variable unit running costs (Taillard, 1999).

The third one, called the VRP with a heterogeneous fleet of vehicles (Toth et al., 2002), generalizes the second version by limiting the number of available vehicles of each type.

The remaining part of the paper is organized as follows: the next section introduces the notation used throughout the paper and describes the variants of heterogeneous VRPs studied in the literature then we introduce our problem: Multi-depot Fleet Size and Mix vehicle Routing Problem with time window. In section 3 we present the mathematical formulation of our own extension of the problem. Then, in the fourth part, we define our resolution method to satisfy our constraints, after that we implement our approach in MATLAB. The computational results for the benchmark instances are analyzed in Section 6. Finally, in section 7 draws the conclusion and future scope of the application.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2021): Forthcoming, Available for Pre-Order
Volume 7: 2 Issues (2020): Forthcoming, Available for Pre-Order
Volume 6: 2 Issues (2019)
Volume 5: 2 Issues (2018)
Volume 4: 2 Issues (2017)
Volume 3: 2 Issues (2016)
Volume 2: 2 Issues (2014)
Volume 1: 2 Issues (2012)
View Complete Journal Contents Listing