Hybrid optimization approach based on gravitational analogy and particle swarm for solving single vehicle pickup and del.pdf The truck dispatching problem is the first example of vehicle routing problems (VRP) [1]. Many modifications of the VRP were examined since then. Information about VRP research is accumulating in [2]. In this article, we consider one of the variants of VRP is called the pickup and delivery problem with single vehicle (SPDP). The problem requires constructing the shortest cyclic route for delivery of homogeneous cargo (e.g. passengers) from all the producers to specific customers with one capacitated vehicle. This problem is classified as NP-hard. The alternative names of SPDP are Pickup-Delivery Traveling Salesman Problem and Traveling Salesman Problem with Pickups and Deliveries [3]. SPDP without vehicle capacity constraint and cargo weights was solved with exact approach in [4]. Example with 15 nods was solved with the combination of branch-and-cuts and greed search algorithms. Authors of [5] and [6] applied different approaches with perturbations in cycles to solve SPDP without vehicle capacity constraint and cargo weights. Approaches were used on a group of 108 examples from TSPLIB, including the example with 441 nods. Algorithms, based on real world analogies, were applied to various variants VRP. In particular, lightning inspired search algorithm (LISA) was proposed in [7]. In [8] it was adapted for the traveling salesman problem. Authors in [9] demonstrated the applicability of another method, called gravity-based algorithm for the multiple traveling salesmen problem. 1. Problem definition Assume, that P = {1,.. .,n} is a set of nodes of cargo pickups and D = {1 + n, ..., 2n} is a set of nodes of cargo deliveries. For the node i from P, the amount of cargo that needs to be picked up is equal qi, while for the node i + n from D the amount of cargo that needs to be delivered is equal to the negative amount (-qi). Set of all the nodes is denoted as V = PUDU{0}, where {0} represents the depot. Distances between all pairs of nodes (cij) are known. A vehicle with the capacity S must visit all the nodes once and deliver cargo from the nodes i to the nodes i + n. A route must start and end in the depot. The goal of the problem is to find the shortest possible route. The problem is AP-hard, because if we assume S = q\\ = ... = qn = 1, then the problem is the equivalent of the asymmetric traveling salesman problem with n + 1 nodes. Minimal allowed vehicle capacity is equal to max{qi}. Clearly, no route could be made if S < max{qi}. If S = max{qi}, there are at least n! allowed routes, for example: 0 - 1 - (1 + n) - 2 - (2 + n) - ... - n - 2n - 0. If vehicle capacity is unlimited, then the number of the allowed routes is equal (2n)!/2n = (2n - 1)!. Number of all permutations is equal (2n)!, and each allowed permutation leads to 2n permutations by switching places of nodes i and i + n for all i = 1, 2, ., n. 52 Hybrid optimization approach based on gravitational analogy and particle swarm With S > max{^| any allowed section of a route could be continued. For example, if the vehicle is empty and there are unvisited clients, then the vehicle can move to some node i to pick up its cargo. Availability of some cargo in the vehicle, means, that some node i is visited, but the cargo is not yet delivered to the node i + n and, as a result, the vehicle can deliver this cargo to the node i + n. Problem formalizations are listed in [10]. 2. Heuristic, based on the gravitational analogy The proposed heuristic procedure is based on the greed algorithm in which the choice of the next destination depends on both a distance between nodes and the cargo size of the corresponding node. Values of pi, i = l,2n, denoting weights, are assigned to the vehicle and every node. These values change during the procedure. Initially, all producer weights are positive, and all consumer weights are equal to zero. Weights are normalized to [0, 1] range. Weight of the vehicle, p0, is equal to the average weight of the producers multiplied on previously defined coefficient R. RA Po =~X, Pi Pi =■ q i+n = 0, i = 1, n, max 9max = max ql, 1fj Coordinates of the particle i in step k + 1 after the move to the selected particle j will be calculated as follows: ((ft - ft)e 'Fu). Parameter Y is an input parameter which value is set before the procedure. Rk+1- Rk +(Rk _Rk).g 1 + i.^rand-lj, _1> 0.01, sk + (sk - sk ). е-ѵІ + 2 ^rand - i j tk +(tk - Rk )• еГіГ + 2 rand - i j -1, if dkt + (dk - dk ) • е ~Fii +1 • ^rand - i< 0 +1, ifdk +(dk - dk )• e~vi + Errand - ^^|> 0 ck +1 _ 5i - ,k+1 _ ti - dk+1 - tk+1 > 1 ? 4 - L 5 (5) (6) (7) (8) where rand is a randomly generated number from 0 to 1. On each step k, the particle with the best solution is registered. The procedure is running until the chosen stopping rule is applied. 4. Computational experiments To conduct numerical experiments, PC with Intel Core i5-4670 3.4GHz, 16Gb RAM and Windows 10 64bit was used. The hybrid procedure was realized in NetBeans IDE 8.1 (Java(TM) SE Runtime Environment 1.8.0_45-b14). For comparative analysis of the models, standard library of symmetrical examples, TSPLIB [11], was used. Nodes coordinates are taken accordingly to data from an example library. Hereafter: - for the examples with even number of nodes, the last node is removed; - for the examples with odd number of nodes, all nodes are used; - first node is depot; - the first half of remaining nodes are producers (i), and the other half are consumers (i + n). For each of the selected examples three types of problems were considered: Type 1: cargo weights of the first half of the producers were equal 1, cargo weights of the second half of the producers were equal 2, i.e. qi = 1, qi+n = -1 (i < n/2), qi = 2, qi+n = -2 (i > n/2). Vehicle capacity S was equal to 2, 6 and 10. Type 2: cargo weights were equal 1, 2, 3, 4 and 5 cyclically. Vehicle capacity S was equal to 5, 10, 15 and 20. Type 3: cargo weights were equal i, i.e. qi = i, qi+n = -i. Vehicle capacity S was equal 3n. For each of the problem two methods were used: enumeration of the values R, s, t and search direction for the heuristic based on the gravitational analogy (HBGA) and hybrid approach. HBGA was performed two times with different discretization. First run of the enumeration (HBGA-1) was performed looking at R from 0.01 to 20 with step 0.01, s from -2 to 2 with step 1, t from 1 to 20 with step 1, both forward and reverse searches. Second run of the enumeration (HBGA-2) was performed looking 54 Hybrid optimization approach based on gravitational analogy and particle swarm at R from 0.1 to 20 with step 0.1, s from -2 to 2 with step 1, t from 1 to 20 with step 1, both forward and reverse searches. In all experiments with the hybrid approach (HA), 20 steps were performed (kmax = 20). Number of particles N was equal 10, 20, 50, 100 and 200. Parameter у was equal 1, 2 and 3. Hybrid procedure was performed once for each set of values N and y. Particles were generated as follows. Parameter R was taken equal to 0.01, 0.03, 0.09, 0.27, 0.81, 2.43, 7.29 and 21.87 cyclically. Parameter s was taken equal to -2, -1, 0, 1 and 2 cyclically. Parameter t was taken equal to 1, 4, 7, 10, 13, 16, 19, 22 and 25 cyclically. Parameter d was taken equal to -1 and 1 cyclically. The difference between path lengths in different approaches is shown in table 1. The length of the path that was found by HBGA-1 for a problem was taken for 100% and other approaches were compared to it. Тable 1 Comparison of path lengths between algorithms Exam ple Type S HBGA-2 HA, N = 10, Y = 1 HA, N = 10, Y = 2 HA, N = 10, Y = 3 HA, N = 20, Y = 1 HA, N = 20, Y = 2 HA, N = 20, Y = 3 HA, N = 50, Y = 1 HA, N = 50, Y = 2 HA, N = 50, Y = 3 HA, N = 100, Y = 1 HA, N = 100, Y = 2 HA, N = 100, Y = 3 HA, N = 200, Y = 1 HA, N = 200, Y = 2 HA, N = 200, Y = 3 rat99 1 4 0,0% 0,0% -0,1% 1,6% 0,5% -0,1% 0,0% 0,0% 0,0% 0,0% -0,1% 0,7% 0,6% -0,1% -0,1% 0,0% 6 1,2% 1,8% 0,3% 3,2% 1,8% 1,2% 0,0% 1,3% 1,3% 1,1% 0,3% 1,3% 0,1% 1,1% 1,2% 1,2% 10 0,2% 0,2% 1,3% 0,2% 0,2% 0,0% 0,2% -0,6% 0,2% 0,2% 0,2% 0,2% 0,2% -0,5% -0,5% -0,5% 2 5 0,0% 0,8% 1,0% 1,0% 0,8% 0,8% 0,8% 0,8% 0,3% 0,8% 0,0% 0,8% 0,0% 0,0% 0,0% 0,0% 10 0,0% 0,0% 1,5% 0,1% 0,4% 0,0% 1,2% 0,6% 0,4% 0,4% 0,1% 0,0% 0,4% 0,1% 0,3% 0,3% 15 0,0% 0,1% 1,6% 1,6% 0,0% 0,1% 0,0% 0,7% 0,0% 0,1% 0,0% 0,1% 0,0% 0,0% 0,0% 0,0% 20 0,0% 2,0% 2,0% 0,0% 0,5% 1,1% 2,0% 0,5% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 3 3*n 0,6% 0,9% 5,8% 0,6% 3,3% 0,6% 2,5% 0,6% 0,6% 1,3% 0,0% 0,6% 0,0% 0,6% 0,6% 1,0% gr137 1 4 0,0% 0,1% 0,4% 0,1% 0,0% 0,0% 0,1% 0,0% 0,1% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 6 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 10 0,0% 3,0% 1,4% 2,5% 2,5% 3,0% 0,7% 0,7% 0,4% 1,4% 0,5% 0,6% 0,0% 0,6% 0,6% 0,0% 2 5 0,0% 0,2% 0,3% 0,2% 0,0% -0,1% 0,0% -0,3% 0,0% -0,3% -0,1% 0,0% 0,0% -0,3% -0,3% -0,3% 10 0,0% 1,2% 0,4% 0,0% 0,0% 0,4% 0,2% 0,0% 1,2% 0,2% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 15 0,2% 0,2% 0,3% 0,7% -0,7% -0,7% 0,2% -0,7% 0,2% -0,7% 0,2% -0,7% -0,7% -0,7% -0,7% -0,7% 20 1,7% 1,7% 1,7% 3,6% 2,4% 3,6% 2,4% 1,7% 1,7% 1,7% 0,8% 1,7% 0,0% 0,0% 0,0% 1,6% 3 3*n 0,3% 2,9% 2,1% 0,7% 0,3% 0,3% 0,3% 1,1% 1,1% 0,3% 0,3% 0,3% 0,3% 0,3% 0,3% 0,3% gr229 1 4 0,0% 0,1% 0,7% 0,6% 0,2% 0,3% 0,4% 0,1% 0,1% -0,1% 0,4% 0,2% 0,2% 0,2% 0,1% 0,1% 6 0,0% 1,0% 0,1% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 10 0,0% 1,8% 1,8% 2,0% 2,5% 0,8% 0,8% 0,0% 2,0% 1,0% 0,9% 0,0% 0,0% 0,1% 0,1% 0,0% 2 5 0,0% 0,8% 0,4% 4,5% 0,7% 0,0% 0,4% 0,7% 0,6% 0,0% 0,0% 0,4% 0,0% 0,4% 0,0% 0,4% 10 0,0% 1,9% 2,1% 2,2% 1,5% 1,5% 1,9% 0,3% 1,4% 1,5% 1,0% 0,8% 1,4% 0,8% 1,1% 0,6% 15 0,0% 0,2% 0,2% 0,2% 0,0% 0,0% 0,0% 0,1% 0,0% 0,1% 0,0% 0,0% 0,0% 0,0% 0,0% 0,0% 20 0,0% 4,2% 4,1% 4,2% 4,1% 4,1% 4,2% 2,7% 0,0% 3,7% 3,7% 2,6% 3,7% 3,7% 0,1% 2,7% 3 3*n 0,0% 0,2% 1,0% 0,2% 0,1% 0,9% 0,0% 0,2% 0,2% 0,0% 0,0% 0,2% 0,2% 0,0% 0,0% 0,0% rd400 1 4 0,0% 3,7% 2,5% 2,5% 2,5% 3,6% 2,2% 2,4% 1,4% 0,0% 2,0% 1,4% 2,4% 1,4% 0,0% 1,4% 6 0,7% 3,2% 1,3% 1,0% 2,9% 3,4% 2,9% -0,8% -0,8% 2,1% 1,3% -0,8% -0,6% -0,8% -0,8% -0,8% 10 0,0% 3,4% 2,2% 0,9% 2,2% 2,6% 0,7% 1,5% -0,2% 0,9% 1,5% 0,7% 0,7% -0,2% 0,7% -0,2% 2 5 0,0% 3,2% 3,2% 3,2% 3,2% 4,6% 4,8% 3,1% 3,1% 3,2% 3,2% 3,1% 3,1% 2,4% 2,4% 3,1% 10 2,9% 7,4% 7,4% 7,0% 6,4% 6,4% 6,4% 6,3% 6,4% 3,1% 5,6% 4,9% 5,1% 3,9% 3,1% 6,2% 15 0,7% 3,9% 5,1% 5,0% 2,8% 3,6% 2,8% 2,7% 2,5% 2,3% 1,6% 1,9% 2,0% 2,1% 0,9% 2,1% 20 0,2% 6,1% 6,4% 2,4% 2,6% 4,0% 1,2% 1,2% 2,4% 2,4% 1,4% 1,7% 1,7% 1,2% 1,7% 0,9% 3 3*n 0,0% 4,4% 5,0% 4,5% 4,4% 4,8% 4,1% 4,9% 5,3% 4,1% 4,1% 3,1% 4,1% 2,7% 3,4% 1,6% pa561 1 4 0,9% 1,5% 2,1% 2,1% 1,6% 2,5% 1,7% 1,0% 1,2% 1,2% 1,7% 0,6% 1,2% 0,0% 0,7% 0,7% 6 0,0% 3,1% 3,1% 4,8% 4,0% 3,6% 4,2% 0,3% 1,9% 2,8% 2,5% 2,8% 0,9% 0,0% 0,6% 0,1% 10 0,0% 2,1% 4,2% 2,5% 1,3% 3,8% 0,0% 1,6% -1,1% 0,8% 0,2% -0,7% 0,8% -0,7% -0,8% -2,0% 2 5 0,0% 1,8% 0,7% 3,0% 2,4% 3,3% 1,4% 1,1% 0,8% 0,4% 0,3% 0,5% 0,3% 0,3% 0,5% 0,5% 10 0,0% 5,3% 6,2% 6,6% 1,3% 3,2% 0,9% 2,1% 0,9% 1,3% 3,3% 0,4% 1,4% 0,7% 0,4% 0,1% 15 0,0% -0,4% 1,4% 2,8% 2,0% 1,2% 1,2% 1,2% 1,2% 0,0% 0,5% 0,1% 1,0% 0,0% 0,1% 0,4% 20 0,0% 2,6% 1,3% 0,1% 0,1% 0,1% 1,3% 1,4% 0,1% 0,0% 0,1% 0,0% 0,0% 0,0% 0,0% 0,0% 3 3*n 0,0% 3,0% 3,0% 2,8% 3,1% 3,6% 3,8% 2,5% 0,2% 2,7% 3,0% 2,5% 0,2% 0,2% 2,5% 1,8% In most examples, HBGA-2 showed same result as HBGA-1. In 30% of examples HBGA-2 showed result worse, than HBGA-1, up to +5% compared to the initial length. 55 R.V. Gindullin The quality of the solutions in hybrid approaches heavily depends on the number of particles N and almost unaffected by y. Parameter у = 3, on average, gave slightly better results than у = 1 and у = 2, but the difference is too small to make a conclusive statement. For N = 10, an average solution was +2% longer than HBGA-1. For N = 50, an average solution was +1% longer than HBGA-1. For N = 200, an average solution was +0.5% longer than HBGA-1. It is worth noting, that, for N = 200, in 12-15% examples hybrid approach resulted with the path length shorter than the path length of HBGA-1. Comparison of the calculation time is shown in table 2. Since there was no significant difference between results for various values of у for HA, only у = 1 is presented in the table 2. Тable 2 Comparison of computational time between algorithms Example Type S HBGA-1 HBGA-2 HA, N = 10, Y = 1 HA, N = 20, Y = 1 HA, N = 50, Y = 1 HA, N = 100, Y = 1 HA, N = 200, Y = 1 rat99 1 4 21,92 2,76 0,03 0,06 0,15 0,30 0,65 6 22,29 3,07 0,03 0,07 0,16 0,33 1,20 10 23,58 3,12 0,04 0,09 0,21 0,53 0,90 2 5 21,95 2,66 0,05 0,08 0,27 0,43 0,82 10 23,44 2,96 0,03 0,06 0,17 0,45 0,78 15 23,95 2,96 0,03 0,07 0,17 0,59 0,88 20 24,27 2,93 0,04 0,12 0,29 0,58 0,81 3 3*n 23,09 2,96 0,03 0,06 0,17 0,34 0,95 gr137 1 4 41,78 5,41 0,13 0,19 0,29 0,75 1,58 6 43,11 6,43 0,06 0,16 0,39 0,76 1,42 10 44,65 6,86 0,06 0,12 0,37 0,62 1,30 2 5 40,64 5,44 0,06 0,11 0,29 0,62 1,17 10 43,33 6,14 0,06 0,12 0,30 0,64 1,24 15 44,54 6,48 0,06 0,13 0,30 0,60 1,26 20 44,19 6,24 0,06 0,14 0,30 0,61 1,25 3 3*n 43,20 6,33 0,06 0,12 0,29 0,61 1,26 gr229 1 4 117,66 17,23 0,17 0,34 0,93 1,85 3,53 6 116,77 16,93 0,16 0,32 0,81 1,73 3,34 10 116,90 15,92 0,16 0,32 0,96 1,82 3,76 2 5 108,85 15,28 0,17 0,32 0,79 1,60 3,47 10 111,82 16,35 0,17 0,31 0,85 1,69 3,81 15 117,01 15,66 0,19 0,36 0,93 1,82 3,67 20 125,66 17,39 0,18 0,34 0,85 1,78 3,77 3 3*n 125,86 16,82 0,19 0,45 0,93 1,89 3,65 rd400 1 4 367,59 51,98 0,61 1,05 2,67 6,23 13,93 6 342,25 50,72 0,70 1,16 2,95 7,12 15,43 10 380,01 51,32 0,50 1,04 2,87 5,77 10,47 2 5 395,55 51,90 0,45 0,96 2,73 5,35 10,54 10 343,70 45,34 0,47 1,08 2,56 5,08 14,50 15 351,94 44,01 0,56 1,29 2,80 7,79 12,97 20 352,15 67,50 0,43 0,84 2,12 4,37 12,49 3 3*n 348,30 63,12 0,54 1,28 3,02 6,23 11,41 pa561 1 4 735,16 87,14 1,17 2,24 7,26 12,99 27,03 6 742,46 96,85 1,19 2,25 6,08 12,79 25,13 10 753,99 97,82 1,19 2,70 7,13 13,47 27,73 2 5 790,23 97,92 1,09 2,54 6,18 14,63 32,16 10 766,68 96,35 1,20 2,39 7,04 14,77 30,12 15 719,73 115,84 1,21 2,88 8,38 13,55 30,92 20 810,83 103,39 1,23 2,58 6,67 14,92 26,39 3 3*n 729,35 112,16 1,34 2,51 6,21 12,57 25,13 56 Hybrid optimization approach based on gravitational analogy and particle swarm Computational time of the hybrid approach changes linearly, depending on the number of particles N, and quadratically, depending on the number of nodes n. With the highest number of particles, N = 200, computational time of HA was 3-4 times lower than the computational time of HBGA-2 and 20-30 times lower than the computational time of HBGA-1. Conclusion The hybrid heuristic approach combining particle swarm optimization and the heuristic, based on the gravitational analogy, for the single vehicle pickup and delivery problem is proposed. The particle swarm optimization is used to estimate optimal parameters for the greed search, based on gravitational analogy. The proposed variant of greed search uses both distances and cargo weights to choose the next destination node. A series of computational experiments was conducted to evaluate properties of the proposed procedure. Computational experiments showed that the hybrid approach is significantly faster than enumeration approach. Both the quality of the solution obtained by the hybrid approach and the computational time required for the approach depend solely on the number of particles used. The proposed approach gives shorter route lengths, than the approach of enumeration of parameters with low discretization, and is faster to perform. The enumeration of parameters with high discretization gives shorter paths in most cases, but the overall difference is not high enough to justify the performance costs, compared to the proposed hybrid approach. The proposed hybrid approach could be used to find an initial solution for other algorithms (e.g., various variants of k-opt). Source code for the proposed approach is available in [12].

Скачать электронную версию публикации