{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T05:14:34Z","timestamp":1783574074123,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,6,8]],"date-time":"2018-06-08T00:00:00Z","timestamp":1528416000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2018,6,8]],"date-time":"2018-06-08T00:00:00Z","timestamp":1528416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:p>We address in this paper a multi-compartment vehicle routing problem (MCVRP) that aims to plan the delivery of different products to a set of geographically dispatched customers. The MCVRP is encountered in many industries, our research has been motivated by petrol station replenishment problem. The main objective of the delivery process is to minimize the total driving distance by the used trucks.\nThe problem configuration is described through a prefixed set of trucks with several compartments and a set of customers with demands and prefixed delivery. Given such inputs, the minimization of the total traveled distance is subject to assignment and routing constraints that express the capacity limitations of each truck\u2019s compartment in terms of the pathways\u2019 restrictions. For the <jats:italic>NP<\/jats:italic>-hardness of the problem, we propose in this paper two algorithms mainly for large problem instances: an adaptive variable neighborhood search (AVNS) and a Partially Matched Crossover PMX-based Genetic Algorithm to solve this problem with the goal of ensuring a better solution quality. We compare the ability of the proposed AVNS with the exact solution using CPLEX and a set of benchmark problem instances is used to analyze the performance of the both proposed meta-heuristics.<\/jats:p>","DOI":"10.1007\/s12351-018-0403-4","type":"journal-article","created":{"date-parts":[[2018,6,8]],"date-time":"2018-06-08T06:48:03Z","timestamp":1528440483000},"page":"2085-2108","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Two metaheuristic approaches for solving the multi-compartment vehicle routing problem"],"prefix":"10.1007","volume":"20","author":[{"given":"Hiba","family":"Yahyaoui","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Islem","family":"Kaabachi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saoussen","family":"Krichen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abdulkader","family":"Dekdouk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,6,8]]},"reference":[{"key":"403_CR1","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.asoc.2015.08.020","volume":"37","author":"MM Abdulkader","year":"2015","unstructured":"Abdulkader MM, Gajpal Y, ElMekkawy TY (2015) Hybridized ant colony algorithm for the multi compartment vehicle routing problem. Appl Soft Comput 37:196\u2013203","journal-title":"Appl Soft Comput"},{"issue":"1","key":"403_CR2","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/S0377-2217(02)00676-8","volume":"152","author":"P Avella","year":"2004","unstructured":"Avella P, Boccia M, Sforza A (2004) Solving a fuel delivery problem by heuristic and exact approaches. Eur J Oper Res 152(1):170\u2013179","journal-title":"Eur J Oper Res"},{"key":"403_CR3","unstructured":"Battarra M, Cordeau J-F, Iori M (2014) Pickup and delivery problems for goods transportation. In: Vehicle routing: problems, methods, and applications, second edition, Chap 6. ISBN: 978-1-61197-358-7"},{"key":"403_CR4","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.cor.2016.06.014","volume":"76","author":"U Breunig","year":"2016","unstructured":"Breunig U, Schmid V, Hartl R, Vidal T (2016) A large neighbourhood based heuristic for two-echelon routing problems. Comput Oper Res 76:208\u2013225","journal-title":"Comput Oper Res"},{"key":"403_CR5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.ins.2016.12.021","volume":"382\u2013383","author":"J Brimberg","year":"2017","unstructured":"Brimberg J, Mladenovi\u0107 N, Todosijevi\u0107 R, sevi\u0107 D\u00a0U (2017) Less is more: solving the max-mean diversity problem with variable neighborhood search. Inf Sci 382\u2013383:179\u2013200","journal-title":"Inf Sci"},{"issue":"Part B","key":"403_CR6","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1016\/j.jhazmat.2016.11.015","volume":"324","author":"GA Bula","year":"2017","unstructured":"Bula GA, Prodhon C, Gonzalez FA, Afsar HM, Velasco N (2017) Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation. J Hazard Mater 324(Part B):472\u2013480","journal-title":"J Hazard Mater"},{"issue":"1","key":"403_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1023\/A:1023067016014","volume":"26","author":"ED Chajakis","year":"2003","unstructured":"Chajakis ED, Guignard M (2003) Scheduling deliveries in vehicles with multiple compartments. J Glob Optim 26(1):43\u201378","journal-title":"J Glob Optim"},{"key":"403_CR28","unstructured":"Christofides PTN, Mingozzi A (1979) The vehicle routing problem, In: Combinatorial optimization. Wiley, Chichester, pp 315\u2013338"},{"issue":"3","key":"403_CR8","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1016\/j.ejor.2014.10.059","volume":"242","author":"LC Coelho","year":"2015","unstructured":"Coelho LC, Laporte G (2015) Classification, models and exact algorithms for multi-compartment delivery problems. Eur J Oper Res 242(3):854\u2013864","journal-title":"Eur J Oper Res"},{"issue":"2","key":"403_CR9","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.ejor.2012.02.007","volume":"220","author":"F Cornillier","year":"2012","unstructured":"Cornillier F, Boctor F, Renaud J (2012) Heuristics for the multi-depot petrol station replenishment problem with time windows. Eur J Oper Res 220(2):361\u2013369","journal-title":"Eur J Oper Res"},{"issue":"5","key":"403_CR10","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1057\/palgrave.jors.2602374","volume":"59","author":"F Cornillier","year":"2008","unstructured":"Cornillier F, Boctor FF, Laporte G, Renaud J (2008) An exact algorithm for the petrol station replenishment problem. J Oper Res Soc 59(5):607\u2013615","journal-title":"J Oper Res Soc"},{"issue":"2","key":"403_CR11","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.ejor.2007.08.016","volume":"191","author":"F Cornillier","year":"2008","unstructured":"Cornillier F, Boctor FF, Laporte G, Renaud J (2008) A heuristic for the multi-period petrol station replenishment problem. Eur J Oper Res 191(2):295\u2013305","journal-title":"Eur J Oper Res"},{"issue":"3","key":"403_CR12","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1016\/j.cor.2007.11.007","volume":"36","author":"F Cornillier","year":"2009","unstructured":"Cornillier F, Laporte G, Boctor FF, Renaud J (2009) The petrol station replenishment problem with time windows. Comput Oper Res 36(3):919\u2013935","journal-title":"Comput Oper Res"},{"issue":"1\u201312","key":"403_CR13","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1016\/S0031-8914(53)80099-6","volume":"19","author":"P Dirac","year":"1953","unstructured":"Dirac P (1953) The lorentz transformation and absolute time. Physica 19(1\u201312):888\u2013896","journal-title":"Physica"},{"issue":"2","key":"403_CR14","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1016\/j.ejor.2015.08.035","volume":"249","author":"M Elbek","year":"2016","unstructured":"Elbek M, W\u00f8hlk S (2016) A variable neighborhood search for the multi-period collection of recyclable materials. Eur J Oper Res 249(2):540\u2013550","journal-title":"Eur J Oper Res"},{"issue":"5","key":"403_CR15","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1016\/j.cor.2006.10.006","volume":"35","author":"AE Fallahi","year":"2008","unstructured":"Fallahi AE, Prins C, Calvo RW (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 35(5):1725\u20131741","journal-title":"Comput Oper Res"},{"key":"403_CR17","unstructured":"Goldberg D, Lingle R (1985) Alleles, loci and the traveling salesman problem. In: Proceedings of the 1st international conference on genetic algorithms and their applications, Los Angeles, pp 154\u2013159"},{"key":"403_CR18","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/j.eswa.2016.09.002","volume":"66","author":"SRA Haddadene","year":"2016","unstructured":"Haddadene SRA, Labadie N, Prodhon C (2016) A grasp x ils for the vehicle routing problem with time windows, synchronization and precedence constraints. Expert Syst Appl 66:274\u2013294","journal-title":"Expert Syst Appl"},{"issue":"4","key":"403_CR19","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10288-008-0089-1","volume":"6","author":"P Hansen","year":"2008","unstructured":"Hansen P, Mladenovi\u0107 N, Moreno\u00a0P\u00e9rez J\u00a0A (2008) Variable neighbourhood search: methods and applications. 4OR 6(4):319\u2013360","journal-title":"4OR"},{"issue":"3","key":"403_CR20","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.ejor.2007.02.002","volume":"191","author":"P Hansen","year":"2008","unstructured":"Hansen P, Mladenovi\u0107 N, P\u00e9rez JAM (2008) Variable neighborhood search. Eur J Oper Res 191(3):593\u2013595","journal-title":"Eur J Oper Res"},{"key":"403_CR21","unstructured":"Kaabachi I, Yahyaoui H, Dekdouk A, Krichen S (2016) A multi-operator genetic algorithm for the multi-compartments vehicle routing problem. In: The 6th international conference on information systems, logistics and supply chain, June 1\u20134, Bordeaux, France (Indexed by EI, INSPEC, DBLP and Thomson ISI)"},{"key":"403_CR22","first-page":"98","volume":"1","author":"N Kumar","year":"2012","unstructured":"Kumar N, Karambir RK (2012) A comparative analysis of pmx, cx and ox crossover operators for solving travelling salesman problem. Int J Latest Res Sci Technol 1:98\u2013101","journal-title":"Int J Latest Res Sci Technol"},{"key":"403_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.omega.2014.08.007","volume":"51","author":"R Lahyani","year":"2015","unstructured":"Lahyani R, Coelho LC, Khemakhem M, Laporte G, Semet F (2015) A multi-compartment vehicle routing problem arising in the collection of olive oil in tunisia. Omega 51:1\u201310","journal-title":"Omega"},{"key":"403_CR24","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.asoc.2016.02.040","volume":"43","author":"K Li","year":"2016","unstructured":"Li K, Tian H (2016) A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem. Appl Soft Comput 43:469\u2013479","journal-title":"Appl Soft Comput"},{"issue":"11","key":"403_CR26","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107 N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097\u20131100","journal-title":"Comput Oper Res"},{"issue":"1","key":"403_CR27","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ejor.2010.02.020","volume":"206","author":"L Muyldermans","year":"2010","unstructured":"Muyldermans L, Pang G (2010) On the benefits of co-collection: experiments with a multi-compartment vehicle routing algorithm. Eur J Oper Res 206(1):93\u2013103","journal-title":"Eur J Oper Res"},{"issue":"9","key":"403_CR29","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1057\/palgrave.jors.2602464","volume":"59","author":"WL Ng","year":"2008","unstructured":"Ng WL, Leung SCH, Lam JKP, Pan SW (2008) Petrol delivery tanker assignment and routing: a case study in hong kong. J Oper Res Soc 59(9):1191\u20131200","journal-title":"J Oper Res Soc"},{"issue":"10","key":"403_CR30","doi-asserted-by":"publisher","first-page":"3213","DOI":"10.1016\/j.cor.2007.02.021","volume":"35","author":"J Oppen","year":"2008","unstructured":"Oppen J, L\u00f8kketangen A (2008) A tabu search approach for the livestock collection problem. Comput Oper Res 35(10):3213\u20133229","journal-title":"Comput Oper Res"},{"key":"403_CR31","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tre.2016.07.006","volume":"94","author":"G Paredes-Belmar","year":"2016","unstructured":"Paredes-Belmar G, Marianov V, Bronfman A, Obreque C, Ler-Villagra A (2016) A milk collection problem with blending. Transp Res Part E: Logist Transp Rev 94:26\u201343","journal-title":"Transp Res Part E: Logist Transp Rev"},{"issue":"18","key":"403_CR32","doi-asserted-by":"publisher","first-page":"13390","DOI":"10.1016\/j.eswa.2012.05.064","volume":"39","author":"D Popovi\u0107","year":"2012","unstructured":"Popovi\u0107 D, Vidovi\u0107 M, Radivojevi\u0107 G (2012) Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. Expert Syst Appl 39(18):13390\u201313398","journal-title":"Expert Syst Appl"},{"issue":"2","key":"403_CR33","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/j.ejor.2016.09.030","volume":"258","author":"E Rahimian","year":"2017","unstructured":"Rahimian E, Akartunali K, Levine J (2017) A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems. Eur J Oper Res 258(2):411\u2013423","journal-title":"Eur J Oper Res"},{"key":"403_CR34","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.asoc.2013.10.017","volume":"15","author":"M Reed","year":"2014","unstructured":"Reed M, Yiannakou A, Evering R (2014) An ant colony algorithm for the multi-compartment vehicle routing problem. Appl Soft Comput 15:169\u2013176","journal-title":"Appl Soft Comput"},{"key":"403_CR35","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cie.2016.12.017","volume":"106","author":"Y Wang","year":"2017","unstructured":"Wang Y, Chen Y, Lin Y (2017) Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem. Comput Ind Eng 106:105\u2013122","journal-title":"Comput Ind Eng"}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-018-0403-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12351-018-0403-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-018-0403-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,10]],"date-time":"2020-10-10T05:05:24Z","timestamp":1602306324000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12351-018-0403-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,8]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["403"],"URL":"https:\/\/doi.org\/10.1007\/s12351-018-0403-4","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"value":"1109-2858","type":"print"},{"value":"1866-1505","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,8]]},"assertion":[{"value":"27 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}