##
**Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries.**
*(English)*
Zbl 1251.90065

Summary: In parallel with the growth of both domestic and international economies, there have been substantial efforts in making manufacturing and service industries more environmental friendly (i.e., promotion of environmental protection). Today manufacturers have become much more concerned with coordinating the operations of manufacturing (for new products) and recycling (for reuse of resources) together with scheduling the forward/reverse flows of goods over a supply chain network. The stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries (STT-VRPSPD) is one of the major operations problems in bi-directional supply chain research. The STT-VRPSPD is a very challenging and difficult combinatorial optimization problem due to many reasons such as a non-monotonic increase or decrease of vehicle capacity and the stochasticity of travel times. In this paper, we develop a new scatter search (SS) approach for the STT-VRPSPD by incorporating a new chance-constrained programming method. A generic genetic algorithm (GA) approach for STT-VRPSPD is also developed and used as a reference for performance comparison. The Dethloff data will be used to evaluate the performance characteristics of both SS and GA approaches. The computational results suggest that the SS solutions are superior to the GA solutions.

### MSC:

90B06 | Transportation, logistics and supply chain management |

90C10 | Integer programming |

90C15 | Stochastic programming |

### Keywords:

stochastic travel-time vehicle routing problem (STT-VRP); integer programming; VRP with simultaneous pick-ups and deliveries (VRPSPD); genetic algorithm (GA); scatter search (SS)
PDFBibTeX
XMLCite

\textit{T. Zhang} et al., Comput. Oper. Res. 39, No. 10, 2277--2290 (2012; Zbl 1251.90065)

Full Text:
DOI

### References:

[1] | Dethloff, J., Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls, Journal of the Operational Research Society, 53, 1, 115-118 (2002) · Zbl 1138.90335 |

[2] | Anily., S., The vehicle-routing problem with delivery and back-haul options, Naval Research Logistics, 43, 3, 415-434 (1996) · Zbl 0846.90035 |

[3] | Min, H., The multiple vehicle routing problems with simultaneous delivery and pick-up points, Transportation Research A, 23, 5, 377-386 (1989) |

[4] | Halse, K. Modeling and solving complex vehicle routing problems. Ph.D. thesis. Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Lyngby, 1992.; Halse, K. Modeling and solving complex vehicle routing problems. Ph.D. thesis. Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Lyngby, 1992. |

[5] | Fisher, M. L.; Tang, B.; Zheng, Z., A network flow based heuristic for bulk pickup and delivery routing, Transportation Science, 29, 45-55 (1994) · Zbl 0826.90042 |

[6] | Savelsbergh, M. W.P.; Sol, M., The general pickup and delivery problem, Transportation Science, 29, 1, 17-29 (1995) · Zbl 0826.90049 |

[7] | Gendreau, M.; Laporte, G.; Vigo, D., Heuristics for the traveling salesman problem with pickup and delivery, Computers and Operations Research, 26, 7, 699-714 (1999) · Zbl 0957.90069 |

[8] | Dethloff, J., Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum, 23, 1, 79-96 (2001) · Zbl 1015.90022 |

[9] | Salhi, S.; Nagy, G., A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50, 1034-1042 (1999) · Zbl 1054.90523 |

[10] | Tang Montané, F. A.; Galvão, R. D., Vehicle routing problems with simultaneous pick-up and delivery service, Journal of the Operations Research Society of India (OPSEARCH), 39, 1, 19-33 (2002) · Zbl 1278.90419 |

[11] | Tang Montané, F. A.; Galvão, R. D., A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Computer and Operations Research, 33, 3, 595-619 (2006) · Zbl 1077.90058 |

[12] | Gronalt, M.; Hartl, R. F.; Reimann, M., New saving based algorithms for time constrained pickup and delivery of full truckloads, Euorpean Jounral of Operational Research, 15, 520-535 (2003) · Zbl 1045.90006 |

[13] | Salhi, S.; Nagy, G., Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, 162, 1, 126-141 (2005) · Zbl 1132.90380 |

[14] | Zachariadis, E. E.; Tarantilis, C. D.; Kiranoudis., C. T., A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service, Expert Systems with Applications, 36, 2, 1070-1081 (2009) |

[15] | Bianchessi, N.; Righini, G., Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery, Computers & Operations Research, 34, 2, 578-594 (2007) · Zbl 1109.90016 |

[16] | Ai, T. J.; Kachitvichyanukul., V., A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 36, 5, 1693-1702 (2009) · Zbl 1179.90068 |

[17] | Gajpal, Y.; Abad, P., An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup, Computers & Operations Research, 36, 12, 3215-3223 (2009) · Zbl 1176.90290 |

[18] | Subramanian, A.; Drummond, L. M.A.; Bentes, C.; Ochi, L. S.; Farias, R., A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 37, 11, 1899-1911 (2010) · Zbl 1188.90041 |

[19] | Çatay, B., A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery, Expert Systems with Applications, 37, 6809-6817 (2010) |

[20] | Kao, E. P.C., A preference order dynamic program for a stochastic traveling salesman problem, Operations Research, 26, 6, 1033-1045 (1978) · Zbl 0419.90080 |

[21] | Sniedovich, M., Technical note—analysis of a preference order traveling salesman problem, Operations Research, 29, 6, 1234-1237 (1981) · Zbl 0474.90068 |

[22] | Carraway, R. L.; Morin, T. L.; Moskovitz, H., Generalized dynamic programming for stochastic combinatorial optimization, Operations Research, 37, 5, 819-829 (1989) · Zbl 0693.90075 |

[23] | Laporte, G.; Louveaux, F.; Mercure., H., The vehicle routing problem with stochastic travel times, Transportation Science, 26, 3, 161-170 (1992) · Zbl 0761.90035 |

[24] | Park, Y. B.; Song, S., Vehicle scheduling problems with time-varying speed, Computers & Industrial Engineering, 33, 3-4, 853-856 (1997) |

[25] | Xie, B. Research on stochastic vehicle routing problems. Ph.D. thesis, Xinan Jiaotong University, China, 2003.; Xie, B. Research on stochastic vehicle routing problems. Ph.D. thesis, Xinan Jiaotong University, China, 2003. |

[26] | Shao, Z, Gao, S, Wang, S. A hybrid particle swarm optimization algorithm for vehicle routing problem with stochastic travel time. Fuzzy information and engineering, vol. 54. Berlin/Heidelberg: Springer; 2009.p. 566-74.; Shao, Z, Gao, S, Wang, S. A hybrid particle swarm optimization algorithm for vehicle routing problem with stochastic travel time. Fuzzy information and engineering, vol. 54. Berlin/Heidelberg: Springer; 2009.p. 566-74. · Zbl 1211.90036 |

[27] | Woensel, T. V.; Kerbache, L.; Peremans, H.; Vandaele, N., A queueing framework for routing problems with time-dependent travel times, Journal of Mathematical Modelling and Algorithms, 6, 1, 151-173 (2007) · Zbl 1255.90050 |

[28] | Lecluyse, C.; Van Wosensel, T.; Peremans, H., Vehicle routing with stochastic time-dependent travel times, 4OR: A Quarterly Journal of Operations Research, 7, 4, 363-377 (2009) · Zbl 1188.90032 |

[29] | Connors, R. D.; Sumalee, A., A network equilibrium model with travellers’ perception of stochastic travel times, Transportation Research, Part B, 43, 614-624 (2009) |

[30] | Chen, A.; Zhou, Z., The \(α\)-reliable mean-excess traffic equilibrium model with stochastic travel times, Transportation Research, Part B, 44, 493-513 (2010) |

[31] | Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences (S0011-7315), 1, 156-166 (1977) |

[32] | Glover, F., A template for scatter search and path relinking, (Hao, J. K.; Lutton, E.; Ronald, E.; Schoenauer, M.; Snyers, D., Artificial evolution, lecture notes in computer science, 1363 (1998), Springer: Springer Germany), 13-54 |

[33] | Campos, V.; Laguna, M.; Marti, R., Scatter search for the linear ordering problem, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill UK), 331-341 |

[34] | Laguna, M.; Marti, R.; Campos, V., Intensification and diversification with elite tabu search solutions for the linear ordering problem, Computers and Operations Research, 26, 12, 1217-1230 (1998) · Zbl 1016.90081 |

[35] | Campos, V.; Glover, F.; Laguna, M.; Marti, R., An experimental evaluation of a scatter search for the linear ordering problem, Journal of Global Optimization, 21, 4, 397-414 (2001) · Zbl 1175.90424 |

[36] | Campos, V.; Laguna, M.; Marti, R., Context-independent scatter and tabu search for permutation problems, INFORMS Journal on Computing, 17, 1, 111-122 (2005) · Zbl 1239.90109 |

[37] | Glover, F.; Laguna, M.; Marti, R., Scatter search. Advances in evolutionary computing: theory and applications, (Ghosh, A.; Tsutsui, S. (2003), Springer-Verlag: Springer-Verlag New York), 519-537, ISBN:3-540-43330-9 |

[38] | Michalewicz, Z.; Logan, T. D.; Swaminathan, S., Evolutionary operators for continuous convex parameter spaces. In: The 3rd annual conference on evolutionary programming (1994), World Scientific Publishing: World Scientific Publishing River Edge, NJ, p. 84-97 |

[39] | Habiba, D, Nabila, A. Scatter search for SAT and W-MAX-SAT problems. In: The 33rd southeastern symposium on system theory, IEEE, Athens, OH, USA, March, 2001, p. 105-9.; Habiba, D, Nabila, A. Scatter search for SAT and W-MAX-SAT problems. In: The 33rd southeastern symposium on system theory, IEEE, Athens, OH, USA, March, 2001, p. 105-9. |

[40] | Hung, W. N.N.; Song, X., BDD variable ordering by scatter search. Computer design. ICCD proceedings of the international conference on computer design (2001), IEEE Computer Society: IEEE Computer Society Austin, Texas, p. 368-73 |

[41] | Hung, W. N.N.; Song, X.; Aboulhamid, E. M.; Driscoll., M. A., BDD minimization by scatter search, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, IEEE, 21, 8, 974-979 (2002) |

[42] | Hung, WNN, Song, X. On optimal cell assignments in PCS networks. In: The 21st IEEE International Proceedings of the Performance, Computing, and Communications Conference, IEEE, Phoenix, AZ, USA; 2002. p. 225-232.; Hung, WNN, Song, X. On optimal cell assignments in PCS networks. In: The 21st IEEE International Proceedings of the Performance, Computing, and Communications Conference, IEEE, Phoenix, AZ, USA; 2002. p. 225-232. |

[43] | Nebro, AJ, Luna, F, Alba, E. New ideas in applying scatter search to multi-objective optimization. In: Evolutionary multi-criterion optimization (S0302-9743). Lecture Notes in Computer Science. Berlin/Heidelberg: Springer. 2005, vol. 3410. p. 443-58.; Nebro, AJ, Luna, F, Alba, E. New ideas in applying scatter search to multi-objective optimization. In: Evolutionary multi-criterion optimization (S0302-9743). Lecture Notes in Computer Science. Berlin/Heidelberg: Springer. 2005, vol. 3410. p. 443-58. · Zbl 1109.68625 |

[44] | Marti, R.; Lourenco, H.; Laguna, M., Assigning proctors to exams with scatter search, (Laguna, M.; González Velarde, J. L., Computing tools for modeling, optimization and simulation (2000), Kluwer Academic Publishers), 215-227 |

[45] | Laguna, M.; Marti, R., Experimental testing of advanced scatter search designs for global optimization of multimodal functions, Journal of Global Optimization, 33, 2, 235-255 (2005) · Zbl 1093.90092 |

[46] | Beausoleil, R. P., MOSS multiobjective scatter search applied to non-linear multiple criteria optimization, European Journal of Operational Research (S0377-2217), 169, 2, 426-449 (2005) · Zbl 1079.90120 |

[47] | Molina, J.; Laguna, M.; Marti, R.; Caballero., R., SSPMO: A scatter tabu search procedure for non-linear multiobjective optimization, Informs Journal on Computing (S0899-1499), 19, 1, 91-100 (2007) · Zbl 1241.90137 |

[48] | Francois, J. L.; Martin-del-Campo, C.; Morales, L. B., Development of a scatter search optimization algorithm for boiling water reactor fuel lattice design, Nuclear Science and Engineering (S0029-5639), 155, 3, 367-377 (2007) |

[49] | Krishna, A. G.; Rao, K. M., Multi-objective optimization of surface grinding operations using scatter search approach, International Journal of Advanced Manufacturing Technology (S0268-3768), 29, 5, 475-480 (2006) |

[50] | Blazewicz, J.; Glover, F.; Kasprzak, M., DNA sequencing-tabu and scatter search combined, Informs Journal on Computing (S0899-1499), 16, 3, 232-240 (2004) · Zbl 1239.90107 |

[51] | Trafalis, T. B.; Kasap, S., A novel metaheuristics approach for continuous global optimization, Journal of Global Optimization (S0925-5001), 23, 2, 171-190 (2002) · Zbl 1175.90320 |

[52] | Santana-Quintero, LV, Ramirez, N, Coello., CC. A multi-objective particle swarm optimizer hybridized with scatter search. In: The 5th Mexican international conference on artificial intelligence. Apizaco, Mexico, November 13-17, Lecture Notes in Artificial Intelligence. 2006, vol. 4293. p. 294-304.; Santana-Quintero, LV, Ramirez, N, Coello., CC. A multi-objective particle swarm optimizer hybridized with scatter search. In: The 5th Mexican international conference on artificial intelligence. Apizaco, Mexico, November 13-17, Lecture Notes in Artificial Intelligence. 2006, vol. 4293. p. 294-304. |

[53] | Russell, R.; Chiang, W., Scatter search for the vehicle routing problem with time windows, European Journal of Operational Research (S0377-2217), 169, 2, 606-622 (2006) · Zbl 1079.90115 |

[54] | Greistorfer, P., A tabu scatter search metaheuristic for the arc routing problem, Computers & Industrial Engineering (S0360-8352), 44, 2, 249-266 (2003) |

[55] | Keskin, B. B.; Uster, H., A scatter search-based heuristic to locate capacitated transshipment points, Computers & Operations Research (S0305-0548), 34, 10, 3112-3125 (2007) · Zbl 1185.90134 |

[56] | Alvarez, A. M.; González-Velarde, J. L.; De-Alba, K., Scatter search for network design problem, Annals of Operations Research (S0254-5330), 138, 1, 159-178 (2005) · Zbl 1091.90006 |

[57] | Gutierrez, MA de-los-Cobos, AS, Goddard, J. A comparison between scatter search and the RAND method for solving the joint replenishment problem. In: The 5th Mexican international conference on artificial intelligence. Leipzig, Apizaco, Mexico, Lecture Notes in Artificial Intelligence, November 13-November 17, 2005. p. 287-95.; Gutierrez, MA de-los-Cobos, AS, Goddard, J. A comparison between scatter search and the RAND method for solving the joint replenishment problem. In: The 5th Mexican international conference on artificial intelligence. Leipzig, Apizaco, Mexico, Lecture Notes in Artificial Intelligence, November 13-November 17, 2005. p. 287-95. |

[58] | Gonzalez, B.; Adenso-Diaz, B., A scatter search approach to the optimum disassembly sequence problem, Computers & Operations Research (S0305-0548), 33, 6, 1776-1793 (2006) · Zbl 1087.90045 |

[59] | Nowicki, E.; Smutnicki, C., Some aspects of scatter search in the flow-shop problem, European Journal of Operational Research (S0377-2217), 169, 2, 654-666 (2005) · Zbl 1079.90058 |

[60] | Alvarez-Valdes, R.; Crespo, E.; Tamarit., J. M., A scatter search algorithm for project scheduling under partially renewable resources, Journal of Heuristics (S1381-1231), 12, 1-2, 95-113 (2006) · Zbl 1122.90036 |

[61] | Rahimi-Vahed, A. R.; Rabbani, M.; Tavakkoli-Moghaddam., R., A multi-objective scatter search for a mixed-model assembly line sequencing problem, Advanced Engineering Informatics (S1474-0346), 21, 1, 85-99 (2007) |

[62] | Zhang, T.; Tian, W.; Zhang, Y.; Liu, S., The improved ant colony algorithm for the VRPSPD with maximum distance constraint, Systems engineering-theory & Practice, 28, 1, 132-140 (2008) |

[63] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581 (1964) |

[64] | Holland, J. H., Adaptation in natural and artificial systems (1992), MIT Press: MIT Press Cambridge, Massachusetts |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.