In the VRP with pickup and delivery, a heterogeneous vehicle fleet based at multiple terminals must satisfy a set of transportation requests. Each request is defined by a pickup point, a corresponding delivery point. The objective function(s) generally minimizes system costs. The early work on VRPPD was conducted for dial-a-ride scenarios [1G. Desaulniers, J. Desrosiers, A. Erdmann, M.M. Solomon, and F. Soumis, "VRP with pickup and delivery", In: Vehicle Routing Problem, Society for Industrial and Applied Methematics: Philadelphia, USA, 2002, pp. 225-242.
[http://dx.doi.org/10.1137/1.9780898718515.ch9] ]. It was first examined by Wilson et al. [2H. Wilson, J. Sussman, H. Wang, and B. Higonnet, "Scheduling algorithms for dial-a-ride systems", In: Tech Report USL TR-70-13, Urban Systems Laboratory, MIT: Cambridge, MA, 1971.], Wilson and Weissberg [3H. Wilson, and H. Weissberg, "Advanced dial-a-ride algorithms research project: final report", In: Tech Report R76-20, Department of Civil Engineering, MIT: Cambridge, MA, 1976.], and was motivated by the demand-responsive transportation systems. A parallel insertion heuristic similar to that of Wilson et al. was proposed by Roy et al. [4S. Roy, J.M. Rousseau, G. Lapalme, and J.A. Ferland, "Routing and scheduling for the transportation of disabled persons-the algorithm", In: Tech Report TP 5596E, Centre de Recherche sur les Transports, Montreal, Canada, 1984.] for the multiple VRPPD in the context of the transportation of disabled persons. Since a fair amount of requests are known in advance, these are used by means of time-spatial proximity criteria to create initial routes for all vehicles starting at the beginning of the day. Madsen, Ravn, and Rygaard [5O.B. Madsen, H.F. Ravn, and J.M. Rygaard, "A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives", Annals of Operation Research, vol. 60, pp. 193-208, 1995.
[http://dx.doi.org/10.1007/BF02031946] ] implemented a generalized version of this approach for a partly dynamic dial-a-ride problem. Their algorithm can minimize vehicle waiting time as well as introduce breaks. Local search for the VRPPD was first considered by Psarafits [6T. Ning, C. Guo, and R. Chen, "A novel method for dynamic vehicle routing problem", Open Cybernetics & Systemic Journal, vol. 9, no. 15, pp. 1-5, 2015.], who extended the ideas of Lin and Kernighan. A decade later, Bent R and Hentenryck presented another local search heuristic for the VRPPD [7T. Ning, R. Chen, C. Guo, and X. Liang, "A scheduling strategy for dynamic vehicle routing problem base on double chains coding", Operations Research Transactions, vol. 19, no. 2, pp. 72-83, 2015.]. The algorithm involves two phases, both using arc exchange procedures. In the construction phase, it tries to find an initial feasible route allowing infeasibility and penalizing the violation of restrictions in the objective function. The VRPPD has a variety of practical applications, including the transport of the disabled and elderly, sealift and airlift of cargo and troops, and pickup and delivery for overnight carriers or urban services. Perspectives on this growing field were offered by Solomon and Desrosiers, et al. [8J. Desrosiers, Y. Dumas, M.M. Solomon, and F. Soumis, "Time constrained routing and scheduling", In: Handbooks in Operations Research and Management Science 8, Network Routing, North-Holland: Amsterdam, 1995, pp. 35-139.].

This paper proposes an improved quantum genetic algorithm based on different constraint conditions at first. Then the non dominated sorting strategy is introduced to obtain more optimal solutions. The effectiveness is verified through the application to the CMTnX and CMTnY. Here we extend the above efforts by reviewing important recent developments and offering our view for future directions.

Identify request i by two nodes, i and n+i, corresponding, respectively, to the pickup and delivery stops of request. It is possible that different nodes may represent the same geographical location. Next, denote the set of pickup nodes by P={1,…,n} and the set of delivery nodes by D={n+1,…, 2 n }. Further, define N=P D. If request i consists of transporting d_i units from i to n+i, let l_i=d_i and l_n+i=-d_i.

Let K be the set of vehicles. Because not all vehicles can service all requests, each vehicle k has a specific set N_k=P_k U D_k associated with it, where N_k, P_k, and D_k are appropriate subsets of N, P, and D, respectively. For each vehicle k, define now network G_k =(V_k, A_k). Set V_k=N_k{o(k), d(k)} as the set of nodes inclusive of the origin, o(k), and destination, d(k), depots for vehicle k, respectively. The subset A_k of V_k × V_k comprise all feasible arcs. The capacity of vehicle k is given by C_k, and its travel time and cost between distinct nodes i, j v_k, by t_ijk and c_ijk, respectively.

The mathematical model of VRPPD may be described as follows:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

The significance of symbol in the mathematical model is as follows:

x is a path, y is a path state, f_k is the fixed cost of vehicle k, p_k is the travel cost of vehicle k in per km, M is the number of customers, K is the number of vehicles which are providing the service, d_ij is the distance between customer i and customer j, Q is the maximum loads of vehicles, q_i is the delivery quantity for the customer i, p_i is the pickup quantity for the customer i, v is the ratio between goods volume and the maximum load when the vehicle is to leave the distribution center, U_ik is the load of vehicle k after leaves the customer i, P is ratio between pickup and delivery.

Eq. (1) is the objective function includeing the fixed cost and travel cost for the vehicle, is the total fixed cost and is the total travel cost.

Eq. (2) is the leaving of vehicle k from i to j. Eq. (3) indicates that vehicle k is serving the customer i. Eq. (4) indicates that the customer i can be served only by vehicle k. Eq. (5) indicates that any customer can be served only once at most. Eq. (6) indicates that the total load of vehicle k can not exceed its capacity of Q. Eq. (7) indicates that the initial loading rate of vehicle k should be less than 1 to reserve some space for pickup. Eq. (8) indicates that the total volume of the goods in vehicle k can not exceed the upper limit. Eq. (9) indicates that the pickup service should be executed in the completion of a certain amount of delivery service, so as to minimize the cost of cargo handing.

Quantum genetic algorithm (QGA) realized the diversity and parallelism of the population through replacing the chromosome coding with quantum bits probability amplitude and searching with the quantum gates. This paper proposed improved double chains quantum genetic algorithm (IDCQGA) because of there being shortcomings of complex encoding and decoding with QGA.

3.1. Double Chains Quantum Genetic Algorithm

This paper introduces a new compensation factor γ (γ ≥ 1) on the basis of probability amplitude coding, if pi is a quantum chromosome, then the coding scheme of the i^th chromosome is as follows:

(10)

In which the normalization condition should be met for α and β, that is to say, and , rad is the random number in (0,1); i=1,2,…,n; j=1,2,…,m; n is the size of the population, m is the number of the qubit. γ makes the cycle from 2π into multi-cycle to improve the convergence efficiency of the algorithm. Each chromosome consists of two parallel gene chains, and one is the vehicle selecting chain, the other is goods sequencing chain.

The gene chain represents that the sequence number of the elected vehicle with the goods of {G1 G2 G3 G4 G5 G6 G7} is 3-1-2-3-4-3-1, that is to say, the G1 can select any vehicle from the set of V1, V2, V3 and V4, and it can be known that 3 represents the 3^rd vehicle with the name of V3 is selected. G6 can select any vehicle from the set of V1, V3 and V4, and the 3 represents the 3^rd vehicle with the name of V4.

The gene chain represents the sequence of the goods, that is to say, if the numbers of goods are 2-1-4-3-7-5-6, then the corresponding sequence is G2 G1 G4 G3 G7 G5 G6.

In order to evaluate the effectiveness of proposed method, this paper adds some convergence curves. Fig. (1) shows the different convergence speed of obtaining the optimal solutions. The proposed method is compared with some existing algorithms, such as IA (Insert Algorithm) [9M.R. Rao, and S. Ziont, "Allocation of transportation units to alternative trips-A column generation scheme with out-of-kilter sub-problems", Operation Research, vol. 16, no. 1, pp. 52-63, 1968.
[http://dx.doi.org/10.1287/opre.16.1.52] ], TVN (Tabu and variable neighborhood algorithm) [10M.D. Amico, M. Monaci, C. Pagani, and D. Vigo, "Heuristic approaches for the fleet size and mix vehicle routing problem with time windows", Transportation and Science, vol. 41, no. 4, pp. 516-526, 2007.
[http://dx.doi.org/10.1287/trsc.1070.0190] ], and TS (Hybrid tabu search) [11J. Sun, B. Feng, and W. Xu, "Particle swarm optimization with particle having quantum behavior", In: Congress on Evolutionary Computation, 2012, pp. 325-331.]. The results are shown in Fig. (1), in which it can be known that the optimal solution of 45 can be obtained with IDCQGA within 100 iterations. However, the optimal solution of 68 can be obtained with TVN and TS. The method of IA is relatively poor with the solution of 120. From another perspective, the optimal solution can be obtained with IDCQGA in the 22^nd iteration, and it can be obtained with TS in about 34^th iteration, the convergence effectiveness of other algorithms are significantly worse.

The comparison of convergence curves are as follows:

Fig. (1) Comparison of convergence curves.

A multi-objective VRPPD mathematical model is established as per different constraints at first. Next, the double chains quantum genetic algorithm is proposed to generate vehicle chain and goods chain in the early stage of the algorithm. Lastly, In order to obtain more optimal solutions the non dominated sorting strategy is introduced. The comparison results of convergence curves demonstrate that the proposed method can improve the efficiency of iterative search and obtain more non-dominated solutions than the existing algorithms. The above discussion verified the effectiveness of the proposed method.

The authors confirm that this article content has no conflict of interest.