Article Preview
Top1. 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.