بهترین راه حل جدید برای مشکلات معیار VRPSPD توسط الگوریتم مبتنی بر آشفتگی

This paper discusses the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), in which both pickup and delivery tasks simultaneously occur at various customer locations. The objective is to design a set of minimum distance routes with the minimum number of vehicles satisfying all the customers. This paper proposes a heuristic algorithm consisting of a route construction procedure, a route improvement procedure, and a solution perturbation procedure. A new sweep-based route construction method is developed to generate better initial solutions. In the route improvement procedure, a series of inter- and intra-route improvement algorithms are applied. The perturbation procedure perturbs a solution by removing some routes and stops from the solution and reinserting them into the solution. The last procedure is used to escape from local optima. Computational experiments on various benchmark instances are performed to evaluate our algorithm against the previously proposed approaches. New best solutions for many benchmark instances are found.

In the classic vehicle routing problem (VRP), a set of delivery customers with known demands is to be served by a fleet of vehicles from a single distribution center, called a depot. Vehicles have identical capacities, and they all start and end their tour at the depot. The objective is to minimize the total distance traveled by the entire fleet. The problems that need to be solved in real-life situations are usually much more complicated. For example, customers not only have delivery demands, but also pickup demands. Examples of these real-life problems include the VRP with mixed pickup and delivery, the dial-a-ride problem, and the VRP with simultaneous pickup and delivery (VRPSPD). In this paper, we discuss the VRPSPD. The VRPSPD is a variation of the classic VRP, in which clients have both delivery and pickup demands, and each customer should be serviced by a single vehicle. Pickup and delivery should be performed simultaneously such that each customer is visited only once by a vehicle. For the VRPSPD in this paper, the objective is to minimize the total distance traveled by the entire fleet subject to the following considerations: • Each customer should be serviced by a single vehicle. • Each customer has both delivery and pickup demands. Either demand amount may have a value of 0. • If a customer has both pickup and delivery demands, the delivery task is serviced before the pickup task. • All vehicles have the same capacity and the same duration limit. • At any point of a route, the loaded amount, that is, the sum of the up-to-that-point pickup and future-after-that-point delivery amounts cannot exceed the vehicle capacity. • The route duration of a vehicle cannot exceed the vehicle duration limit. • There is a single depot. • All vehicles start from and end at the depot. The VRPSPD was first introduced by Min (1989), who studied the book delivery and pick-up activity between a central library and 22 local libraries with a given number of capacitated vehicles. He proposed a cluster-first route-second approach, in which customer locations are clustered first and then a route for each cluster is generated by a traveling salesman problem (TSP) algorithm. Dethloff (2001) pointed out the importance of the VRPSPD in reverse logistics operations. His solution approach is based on a cheapest insertion method. The insertion criterion of the approach takes into account three metrics: travel distance, residual capacity, and radial surcharge. More recently, Nagy and Salhi (2005) proposed four insertion-based heuristics to solve VRPSPD. After constructing partial routes for a set of customers, the remaining customers are repetitively inserted into the partial routes by the insertion method. Montane and Galvao (2006) proposed a tabu search with a frequency penalization scheme to diversify the search space for VRPSPD. Zachariadis, Tarantilis, and Kiranoudis (2009) proposed a hybrid solution approach incorporating a tabu search and a guided local search. Ai and Kachivichyanukul (2009) presented a mathematical formulation of the VRPSPD and proposed a particle swarm optimization (PSO) algorithm as a solution approach. Zachariadis, Tarantilis, and Kiranoudis (2010) proposed a local search metaheuristic solution approach for the VRPSPD. The proposed algorithm is capable of exploring wide solution neighborhoods by statistically encoding moves into special data structures. They also apply the adaptive memory algorithmic framework which collects and combines promising solution features to generate high-quality solutions. Subramanian, Drummond, Bentes, Ochi, and Farias (2010) proposed a parallel metaheuristic for the VRPSPD, which is a master–worker based parallel model, and has three main parts. The first one estimates the number of vehicles; the second part corresponds to the automatic calibration of the parameter gamma, which is a factor that controls the bonus of inserting clients remotely located from the depot; and the third is the optimization phase. Catay (2010) developed an ant colony algorithm equipped with a new saving-based visibility function and a pheromone update procedure. As the VRP is a very complex NP-hard problem (Golden, Ball, & Bodin, 1981), solving the real-life VRPs to optimality is often not possible within the limited computing time available in practical situations. Therefore, most of the research available has focused on heuristics and metaheuristic solution methods designed to produce high quality solutions within a given time. When all the pick-up demands of customers are set to 0, VRPSPD becomes VRP. The VRPSPD is NP-hard because its special case is NP-hard. Although it has recently drawn increased attention from researchers, it still requires development of better solution approaches. In this paper, we propose a heuristic algorithm consisting of a route construction procedure, a route improvement procedure, and a solution perturbation procedure. A new sweep-based route construction method is developed to generate better initial solutions. The perturbation procedure perturbs a solution by removing some routes and stops from the solution and reinserting them into the solution. The last procedure is used to escape from local optima. Computational experiments on various benchmark instances are performed to evaluate our algorithm against previously proposed approaches. New best solutions for many benchmark instances are found. The remainder of this paper is organized as follows. Section 2 summarizes the main idea of the proposed heuristic algorithm and the improvement heuristics applied within our algorithm. Then we proceed to the description of the main structure of the solution algorithm, the initial solution procedure, improvement procedure and finally the perturbation strategies that are used to improve the initial solution. In Section 3 computational experiments on the benchmark data sets are presented. Section 4 provides conclusions and future research directions.

This paper presents a heuristic approach consisting of route construction, improvement, and perturbation algorithms to solve VRPSPD. To generate a better initial solution, a new sweep variant, called the nearest sweep algorithm, was proposed. In the route improvement procedure, a series of inter-route (m, n) exchange, cross exchange, intra-route 2-opt, and Or-opt algorithms are applied. The perturbation procedure perturbs a solution by removing some routes and stops from the solution and reinserting them into the solution using the Hungarian method. The last procedure is used to escape from local optima. The computational results on some benchmark problems show that the proposed heuristic outperforms the existing algorithms and many new best solutions have been found. The proposed algorithm could find new best solutions for 53 instances and make tie with the existing best known solutions for 6 instances out of 70 benchmark problem instances. The proposed approach can be further applied to many other variants of the VRP.