International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 9, No. 10, 8 Oct. 2017
Cover page and Table of Contents: PDF (size: 906KB)
An Heuristic Approach to Solving the one-to-one Pickup and Delivery Problem with Threedimensional Loading Constraints
Full Text (PDF, 906KB), PP.1-12
Views: 0 Downloads: 0
Author(s)
Remy Dupas
1,*
Igor Grebennik
2
Oleksandr Lytvynenko
2
Oleksij Baranov
2
Index Terms
Pickup and Delivery problem, vehicle routing, 3D loading constraints, combinatorial configuration, generation, packing of parallelepipeds
Abstract
A mathematical model and a solving strategy for the Pickup and Delivery Problem with three-dimensional loading constraints regarding a combinatorial configuration instead of a traditional approach that utilizes Boolean variables is proposed. A traditional one-to-one Pickup and Delivery Problem in a combination with a problem of packing transported items into vehicles by means of the proposed combinatorial generation algorithm is solved.
Cite This Paper
Rémy Dupas, Igor Grebennik, Oleksandr Lytvynenko, Oleksij Baranov, "An Heuristic Approach to Solving the one-to-one Pickup and Delivery Problem with Three-dimensional Loading Constraints", International Journal of Information Technology and Computer Science(IJITCS), Vol.9, No.10, pp.1-12, 2017. DOI:10.5815/ijitcs.2017.10.01
Reference
[1]B. Golden, S. Raghavan, and E. Wasil, The vehicle routing problem: latest advances and new challenges. Springer Science & Business Media, 2008.
[2]V. Pillac, M. Gendreau, C. Guéret, and A. L. Medaglia, “A review of dynamic vehicle routing problems,” European Journal of Operational Research, vol. 225, no. 1, pp. 1–11, Feb. 2013.
[3]S. Kumar and R. Panneerselvam, “A survey on the vehicle routing problem and its variants,” Intelligent Information Management, vol. 4, no. 3, p. 66, 2012.
[4]M. Gendreau, M. Iori, G. Laporte, and S. Martello, “A Tabu Search Algorithm for a Routing and Container Loading Problem,” Transportation Science, vol. 40, no. 3, pp. 342–350, Aug. 2006.
[5]M. Iori and S. Martello, “Routing problems with loading constraints,” TOP, vol. 18, no. 1, pp. 4–27, Jul. 2010.
[6]H. Pollaris, K. Braekers, A. Caris, G. K. Janssens, and S. Limbourg, “Vehicle routing problems with loading constraints: state-of-the-art and future directions,” OR Spectrum, vol. 37, no. 2, pp. 297–330, Mar. 2015.
[7]S. N. Parragh, K. F. Doerner, and R. F. Hartl, “A survey on pickup and delivery problems,” Journal für Betriebswirtschaft, vol. 58, no. 1, pp. 21–51, Apr. 2008.
[8]G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia, and G. Laporte, “Static pickup and delivery problems: a classification scheme and survey,” TOP, vol. 15, no. 1, pp. 1–31, May 2007.
[9]J. Cordeau, G. Laporte, and S. Ropke, “Recent models and algorithms for one-to-one pickup and delivery problems,” in The vehicle routing problem: latest advances and new challenges, vol. 43, 2008, pp. 327–357.
[10]M. W. P. Savelsbergh and M. Sol, “The General Pickup and Delivery Problem,” Transportation Science, vol. 29, no. 1, pp. 17–29, Feb. 1995.
[11]S. Ropke, J.-F. Cordeau, and G. Laporte, “Models and branch-and-cut algorithms for pickup and delivery problems with time windows,” Networks, vol. 49, no. 4, pp. 258–272, 2007.
[12]P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics, 2014.
[13]W. P. Nanry and J. Wesley Barnes, “Solving the pickup and delivery problem with time windows using reactive tabu search,” Transportation Research Part B: Methodological, vol. 34, no. 2, pp. 107–121, Feb. 2000.
[14]H. Li and A. Lim, “A Metaheuristic for the Pickup and Delivery Problem with Time Windows,” International Journal on Artificial Intelligence Tools, vol. 12, no. 2, pp. 173–186, Jun. 2003.
[15]H. Lim, A. Lim, and B. Rodrigues, “Solving the pickup and delivery problem with time windows using issqueaky wheelli optimization with local search,” AMCIS 2002 Proceedings, p. 317, 2002.
[16]G. Pankratz, “A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows,” OR Spectrum, vol. 27, no. 1, pp. 21–41, Jan. 2005.
[17]Q. Lu and M. M. Dessouky, “A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows,” European Journal of Operational Research, vol. 175, no. 2, pp. 672–687, Dec. 2006.
[18]R. Bent and P. Van Hentenryck, “A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows,” Computers & Operations Research, vol. 33, no. 4, pp. 875–893, Apr. 2006.
[19]S. Ropke and D. Pisinger, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science, vol. 40, no. 4, pp. 455–472, Nov. 2006.
[20]Y. Nagata and S. Kobayashi, “A Memetic Algorithm for the Pickup and Delivery Problem with Time Windows Using Selective Route Exchange Crossover,” in Parallel Problem Solving from Nature, PPSN XI, Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 536–545.
[21]J.-F. Côté, M. Gendreau, and J.-Y. Potvin, “Large neighborhood search for the pickup and delivery traveling salesman problem with multiple stacks,” Networks, vol. 60, no. 1, pp. 19–30, Aug. 2012.
[22]G. Erdoğan, J.-F. Cordeau, and G. Laporte, “The pickup and delivery traveling salesman problem with first-in-first-out loading,” Computers & Operations Research, vol. 36, no. 6, pp. 1800–1808, Jun. 2009.
[23]A. Malapert, C. Guéret, and N. Jussien, “Two-dimensional pickup and delivery routing problem with loading constraints,” in First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC’08), 2008.
[24]E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, “The Pallet-Packing Vehicle Routing Problem,” Transportation Science, vol. 46, no. 3, pp. 341–358, Aug. 2012.
[25]D. Männel and A. Bortfeldt, “A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints,” European Journal of Operational Research, vol. 254, no. 3, pp. 840–858, Nov. 2016.
[26]T. Bartók and C. Imreh, “Pickup and Delivery Vehicle Routing with Multidimensional Loading Constraints,” Acta Cybernetica, vol. 20, no. 1, pp. 17–33, 2011.
[27]D. Pisinger and S. Ropke, “A general heuristic for vehicle routing problems,” Computers & Operations Research, vol. 34, no. 8, pp. 2403–2435, Aug. 2007.
[28]G. Scheithauer, Y. G. Stoyan, and T. Y. Romanova, “Mathematical Modeling of Interactions of Primary Geometric 3D Objects,” Cybernetics and Systems Analysis, vol. 41, no. 3, pp. 332–342, May 2005.
[29]I. V. Grebennik, A. V. Pankratov, A. M. Chugay, and A. V. Baranov, “Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped,” Cybernetics and Systems Analysis, vol. 46, no. 5, pp. 793–802, Sep. 2010.
[30]S. K. Ali, Z. Naser Azeez, and A. Abdul-Hussein Ouda, “A New Clustering Algorithm for Face Classification,” International Journal of Information Technology and Computer Science (IJITCS), vol. 8, no. 6, pp. 1–8, 2016.
[31]J. A. Hartigan and M. A. Wong, “Algorithm AS 136: A K-Means Clustering Algorithm,” Applied Statistics, vol. 28, no. 1, p. 100, 1979.
[32]A. C. Fabregas, B. D. Gerardo, and B. T. Tanguilig III, “Enhanced Initial Centroids for K-means Algorithm,” International Journal of Information Technology and Computer Science (IJITCS), vol. 9, no. 1, pp. 26–33, 2017.
[33]A. Chadha and S. Kumar, “Extension of K-Modes Algorithm for Generating Clusters Automatically,” International Journal of Information Technology and Computer Science (IJITCS), vol. 8, no. 3, pp. 51–57, 2016.
[34]Y. Stoyan and I. Grebennik, “Description and Generation of Combinatorial Sets Having Special Characteristics(Bilevel Programming, Optimization Methods, and Applications to Economics),” Biomedical fuzzy and human sciences : the official journal of the Biomedical Fuzzy Systems Association, vol. 18, no. 1, pp. 83–88, 2013.
[35]I. V. Grebennik and O. S. Lytvynenko, “Generating combinatorial sets with given properties,” Cybernetics and Systems Analysis, vol. 48, no. 6, 2012.
[36]B. T. Lowerre, “The HARPY Speech Recognition System.” Carnegie Mellon University, 1976.
[37]I. Sabuncuoglu and M. Bayiz, “Job shop scheduling with beam search,” European Journal of Operational Research, vol. 118, no. 2, pp. 390–412, Oct. 1999.
[38]J. Renaud, F. F. Boctor, and J. Ouenniche, “A heuristic for the pickup and delivery traveling salesman problem,” Computers & Operations Research, vol. 27, no. 9, pp. 905–916, Aug. 2000.
[39]S. Ropke and J.-F. Cordeau, “Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows,” Transportation Science, vol. 43, no. 3, pp. 267–286, Aug. 2009.
[40]I. Grebennik, O. Lytvynenko, and O. Titova, “Optimization of linear function on a set of cyclic permutations,” Bionics of intellect, vol. 2, no. 67, 2012.