Quantum Inspired Algorithm for a VRP with Heterogeneous Fleet Mixed Backhauls and Time Windows

Quantum Inspired Algorithm for a VRP with Heterogeneous Fleet Mixed Backhauls and Time Windows

Meryem Berghida (University of Jijel, Jijel, Algeria) and Abdelmadjid Boukra (University of Science and Technology Houari Boumediene, Bab Ezzouar, Algeria)
Copyright: © 2016 |Pages: 21
DOI: 10.4018/IJAMC.2016100102


This paper presents a new Quantum Inspired Harmony Search algorithm with Variable Population Size QIHSVPS for a complex variant of vehicle routing problem (VRP), called HVRPMBTW (Vehicle Routing Problem with Heterogeneous fleet, Mixed Backhauls and Time Windows). This variant is characterized by a limited number of vehicles with various capacities and costs. The vehicles serve two types of customers: linehauls customers and backhauls customers. Each customer must be visited in a specific interval of time. The authors propose to use quantum principles to accelerate evolution process and variable population size to decrease the number of solution's evaluation, when the improvement is insignificant. This new approach was tested on benchmarks and produces satisfactory results compared to other approaches.
Article Preview

1. Introduction

Researchers may find inspiration in different area to solve difficult problems. Among these problems, there are optimization problems. An optimization problem consists in finding the best solution among a large amount of solutions. This is a problem which we meet daily in the real life, when the shortest path to go to work is chosen every morning, when the furniture of the house is arranged to make more space by keeping beautiful decoration...etc. Optimization is also important in the commercial area; how do you connect all the houses of a new estate with the minimum number of electrical wiring or minimum number of sewer pipes? Or for example, which articles you put in the same range in a supermarket? What is the best route to take for your delivery trucks to the shop with minimum cost (avoiding the traffic jam)? The latter problem known as vehicle routing problem or VRP is the object of this paper. Throughout history, the original version of this problem was proposed by Dantzig and Ramser on 1959 (Dantzig & Ramser, 1959). After the publication of their paper which had the purpose of calculating a set of optimal routes for a fleet of delivery trucks, the VRP has caught the attention of many researchers.

Solving this kind of problems is not easy, especially when you have many options to choose from. Music seems a strange place to look for help in the resolution of this classical optimization problem, but this is where a rather cunning method called “Harmony search” found his inspiration. Harmony Search (HS) algorithm is a metaheuristic developed by, Zong Woo Geem et al. (Geem et al., 2001) in 2001. It imitates the musician searching to find agreeable harmony, just as the optimization process searches to find a global optimal solution using an objective function.

Another area of research called Quantum Computing (Benioff, 1980) has recently emerged. Quantum computing is the sub-field of computer science that deals with quantum computers using the quantum mechanics phenomena. Useful quantum phenomena are quantum entanglement and superposition. Operations are no longer based on the manipulation of bits, but Q-bits. Quantum computing allows designing very efficient algorithms. But, these algorithms cannot be exploited before the construction of quantum machines. Until the construction of these machines, the idea of simulating quantum algorithms on classical computers or combined with other conventional methods has emerged (Draa et al., 2010; Wang et al., 2012; Xiao et al., 2010; Gao & Wang, 2011; Layeb, 2013; Wang & Li, 2010; J.-L. Zhang et al., 2008).

In this paper, we combine variable population size harmony search algorithm with Quantum principles to propose a new metaheuristic named QIHSVPS (Quantum Inspired Harmony Search algorithm with Variable Size Population), to solve a rarely studied variant of VRP called Vehicle Routing Problem with Heterogeneous Fleet, Mixed Backhauls and Time Windows (HVRPMBTW). This problem was taken from the previous works of Belmecheri et al. (Belmecheri et al., 2012). This problem considers two types of customers: customers receiving goods (linehauls customers), and customers returning goods to the depot center (backhauls customers). We note that the goods delivered to the linehauls customers are different from those picked up from backhauls customers. The goods delivered from central depot can be alternated with goods collected. The service at any customer starts within a given time interval (i.e. if a vehicle arrives too early at a customer, it must wait until the time window opens, and it is not allowed to arrive late). Vehicles insuring the service have a different capacities and variable costs.

The remainder of this paper is organized as follows. In section 2, some related works are given. In section 3, we give the mathematical formulation of the problem. Section 4 focuses on the solving approach. Section 5 is devoted to experimental results. The paper is concluded in section 6.

Complete Article List

Search this Journal:
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