Advanced search
Publication Cover
Journal of the Operational Research Society Volume 58, 2007 - Issue 12
Submit an article Journal homepage
491
Views
87
CrossRef citations to date
0
Altmetric
Theoretical Paper

A branch-and-cut algorithm for the capacitated open vehicle routing problem

A N LetchfordLancaster UniversityLancasterUKCorrespondence[email protected]
,
J LysgaardAarhus School of BusinessDenmark
&
R W EgleseLancaster UniversityLancasterUK
Pages 1642-1651 | Received 01 Feb 2006, Accepted 01 Oct 2006, Published online: 21 Dec 2017

Citations (87)

Keep up to date with the latest research on this topic with citation updates for this article.

Subscribe to citation updates

Read on this site (7)

Neri Volpato, Lauro Cesar Galvão, Luiz Fernando Nunes, Rômulo Ianuch Souza & Karina Oguido. (2020) Combining heuristics for tool-path optimisation in material extrusion additive manufacturing. Journal of the Operational Research Society 71:6, pages 867-877.
Read now
Rahma Lahyani, Anne-Lise Gouguenheim & Leandro C. Coelho. (2019) A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems. International Journal of Production Research 57:22, pages 6963-6976.
Read now
Yuankai Zhang, Minfang Huang, Xiangpei Hu & Lijun Sun. (2018) Package consolidation approach to the split-order fulfillment problem of online supermarkets. Journal of the Operational Research Society 69:1, pages 127-141.
Read now
İsmail Karaoğlan & Saadettin Erhan Kesen. (2017) The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm. International Journal of Production Research 55:2, pages 536-557.
Read now
Joanna Bauer & Jens Lysgaard. (2015) The offshore wind farm array cable layout problem: a planar open vehicle routing problem. Journal of the Operational Research Society 66:3, pages 360-368.
Read now
Q Mu, Z Fu, J Lysgaard & R Eglese. (2011) Disruption management of the vehicle routing problem with vehicle breakdown. Journal of the Operational Research Society 62:4, pages 742-749.
Read now
U Derigs & K Reuter. (2009) A simple and efficient tabu search heuristic for solving the open vehicle routing problem. Journal of the Operational Research Society 60:12, pages 1658-1669.
Read now

Articles from other publishers (80)

Vinícius Carvalho Soares & Marcos Roboredo. (2023) On the exact solution of the multi-depot open vehicle routing problem. Optimization Letters 18:4, pages 1053-1069.
Crossref
Jianxia Li, Ruochen Liu & Ruinan Wang. (2024) Handling dynamic capacitated vehicle routing problems based on adaptive genetic algorithm with elastic strategy. Swarm and Evolutionary Computation 86, pages 101529.
Crossref
Yutong Zhang, Hongwei Li, Zhaotu Wang & Huajian Wang. (2024) A Multi-Objective Learning Whale Optimization Algorithm for Open Vehicle Routing Problem with Two-Dimensional Loading Constraints. Mathematics 12:5, pages 731.
Crossref
Yue Li, Jianyou Zhao & Zenghua Chen. (2024) Analyzing the delivery determination problem of new retail stores considering crowdsourcing under the background of blockchain. Research in Transportation Business & Management 52, pages 101083.
Crossref
Themistoklis Stamadianos, Nikolaos A. Kyriakakis, Magdalene Marinaki & Yannis Marinakis. (2023) A hybrid simulated annealing and variable neighborhood search algorithm for the close-open electric vehicle routing problem. Annals of Mathematics and Artificial Intelligence.
Crossref
Venkata Sirimuvva Chirala, Kaarthik Sundar, Saravanan Venkatachalam, Jonathon M. Smereka & Sam Kassoumeh. (2023) Heuristics for Multi-Vehicle Routing Problem Considering Human-Robot Interactions. IEEE Transactions on Intelligent Vehicles 8:5, pages 3228-3238.
Crossref
Jingru Ding. (2023) Review of Research on Vehicle Routing Problem and Related Algorithms. Frontiers in Computing and Intelligent Systems 2:3, pages 106-108.
Crossref
Xianlong Ge & Yuanzhi Jin. (2023) Sustainability Oriented Vehicle Route Planning Based on Time-Dependent Arc Travel Durations. Sustainability 15:4, pages 3208.
Crossref
Tobias Sprodowski, Marit Hoff-Hoffmeyer-Zlotnik & Michael Freitag. (2023) Dimension reduction for a multi-resource general assignment problem by decomposable costs for a vehicle compound. IFAC-PapersOnLine 56:2, pages 11148-11153.
Crossref
Ecem Yucesoy, Elvin Coban & Burcu Balcik. 2023. Handbook for Management of Threats. Handbook for Management of Threats 299 323 .
Xiaoxiao Quan, Yongsheng Pang, Jiansheng Chen, Xianghua Chu & Lina Shangguan. (2022) Open pollution routing problem of logistics distribution in medical union based on differential search algorithm. Scientific Reports 12:1.
Crossref
Erdi Dasdemir, Murat Caner Testik, Diclehan Tezcaner Öztürk, Ceren Tuncer Şakar, Güldal Güleryüz & Özlem Müge Testik. (2022) A multi-objective open vehicle routing problem with overbooking: Exact and heuristic solution approaches for an employee transportation problem. Omega 108, pages 102587.
Crossref
Tengjun Zuo, Yuchen Zhang, Xuekuan Xie, Ke Meng, Ziyuan Tong, Zhao Yang Dong & Yubin Jia. (2022) A Review of Optimization Technologies for Large-scale Wind Farm Planning with Practical and Prospective Concerns. IEEE Transactions on Industrial Informatics, pages 1-14.
Crossref
Tobias Sprodowski, Marit Hoff-Hoffmeyer-Zlotnik & Michael Freitag. (2022) Balance efficient shuttle routing and fast order execution on a vehicle compound. IFAC-PapersOnLine 55:10, pages 61-66.
Crossref
Joanna Ochelska-Mierzejewska & Przemysław Zakrzewski. 2022. Developments in Information & Knowledge Management for Business Applications. Developments in Information & Knowledge Management for Business Applications 231 266 .
Li Zhang, Tingting Chen, Bin Yu & Chenyu Wang. (2021) Suburban Demand Responsive Transit Service With Rental Vehicles. IEEE Transactions on Intelligent Transportation Systems 22:4, pages 2391-2403.
Crossref
Tiago Rodrigues Weller, Daniel Rodrigues Weller, Luiz Carlos de Abreu Rodrigues & Neri Volpato. (2021) A framework for tool-path airtime optimization in material extrusion additive manufacturing. Robotics and Computer-Integrated Manufacturing 67, pages 101999.
Crossref
Yuanzhi Jin, Xianlong Ge & Long Zhang. 2021. Multi-Criteria Decision Analysis for Risk Assessment and Management. Multi-Criteria Decision Analysis for Risk Assessment and Management 177 197 .
Telmo Barros, Alexandra Oliveira, Henrique Lopes Cardoso, Luís Paulo Reis, Cristina Caldeira & João Pedro Machado. 2021. Agents and Artificial Intelligence. Agents and Artificial Intelligence 482 503 .
Wenyu Fan. (2020) Multi-constrained Vehicle Routing Problem Solution based on Adaptive Genetic Algorithm. Multi-constrained Vehicle Routing Problem Solution based on Adaptive Genetic Algorithm.
Binhui Chen, Rong Qu, Ruibin Bai & Wasakorn Laesanklang. (2020) A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes. RAIRO - Operations Research 54:5, pages 1467-1494.
Crossref
José Brandão. (2020) A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research 284:2, pages 559-571.
Crossref
Valeria Soto-Mendoza, Irma García-Calvillo, Efraín Ruiz-y-Ruiz & Jaime Pérez-Terrazas. (2020) A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem. Algorithms 13:4, pages 96.
Crossref
Jens Lysgaard, Ana Dolores López‐Sánchez & Alfredo G. Hernández‐Díaz. (2018) A matheuristic for the MinMax capacitated open vehicle routing problem. International Transactions in Operational Research 27:1, pages 394-417.
Crossref
Ferani E. Zulvia, R.J. Kuo & Dwiyanti Y. Nugroho. (2020) A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products. Journal of Cleaner Production 242, pages 118428.
Crossref
Mauricio Granada, Eliana M. Toro & Ramón Gallego. (2019) An MIP formulation for the open location‐routing problem considering the topological characteristic of the solution‐paths. Networks 74:4, pages 374-388.
Crossref
Reza Tavakkoli-Moghaddam, Mohammadreza Meskini, Hadi Nasseri & Haed Tavakkoli-Moghaddam. (2019) A Multi-Depot Close and Open Vehicle Routing Problem with Heterogeneous Vehicles. A Multi-Depot Close and Open Vehicle Routing Problem with Heterogeneous Vehicles.
Efrain Ruiz, Valeria Soto-Mendoza, Alvaro Ernesto Ruiz Barbosa & Ricardo Reyes. (2019) Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers & Industrial Engineering 133, pages 207-219.
Crossref
Jacek Mandziuk. (2019) New Shades of the Vehicle Routing Problem: Emerging Problem Formulations and Computational Intelligence Solution Methods. IEEE Transactions on Emerging Topics in Computational Intelligence 3:3, pages 230-244.
Crossref
Tasnim Ibn Faiz, Chrysafis Vogiatzis & Md. Noor-E-Alam. (2019) A column generation algorithm for vehicle scheduling and routing problems. Computers & Industrial Engineering 130, pages 222-236.
Crossref
M. Babagolzadeh, A. Shrestha, B. Abbasi, S. Zhang, R. Atefi & A. Woodhead. (2019) Sustainable Open Vehicle Routing with Release-Time and Time-Window: A Two-Echelon Distribution System. IFAC-PapersOnLine 52:13, pages 571-576.
Crossref
Yuvraj Gajpal, Vivek Roy & B.S. Sahay. (2019) Vehicle routing for a mid-day meal delivery distribution system. Heliyon 5:1, pages e01158.
Crossref
Aditya Dixit, Apoorva Mishra & Anupam Shukla. 2019. Harmony Search and Nature Inspired Optimization Algorithms. Harmony Search and Nature Inspired Optimization Algorithms 539 546 .
Uri Lipowezky, Boris Korenfeld & Ianir Ideses. (2018) Solving the Capacitated Open Vehicle Routing Problem Algorithm, Based on Probability Distribution Modelling of Saving Matrix. Solving the Capacitated Open Vehicle Routing Problem Algorithm, Based on Probability Distribution Modelling of Saving Matrix.
R. Lewis & K. Smith-Miles. (2018) A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems. Journal of Discrete Algorithms 52-53, pages 2-17.
Crossref
Xuan Gong, Stefanie Kuenzel & Bikash C. Pal. (2018) Optimal Wind Farm Cabling. IEEE Transactions on Sustainable Energy 9:3, pages 1126-1136.
Crossref
Khosro Pichka, Amirsaman H. Bajgiran, Matthew E.H. Petering, Jaejin Jang & Xiaohang Yue. (2018) The two echelon open location routing problem: Mathematical model and hybrid heuristic. Computers & Industrial Engineering 121, pages 97-112.
Crossref
José Brandão. (2018) Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows. Computers & Industrial Engineering 120, pages 146-159.
Crossref
Richard Eglese & Sofoclis Zambirinis. (2018) Disruption management in vehicle routing and scheduling for road freight transport: a review. TOP 26:1, pages 1-17.
Crossref
Tantikorn Pichpibul. (2018) Modified Elephant Search Algorithm for Distribution of Snack Food in Thailand. Modified Elephant Search Algorithm for Distribution of Snack Food in Thailand.
Gizem Ozbaygin, Oya Karasan & Hande Yaman. (2018) New exact solution approaches for the split delivery vehicle routing problem. EURO Journal on Computational Optimization 6:1, pages 85-115.
Crossref
Reza Atefi, Majid Salari, Leandro C. Coelho & Jacques Renaud. (2018) The open vehicle routing problem with decoupling points. European Journal of Operational Research 265:1, pages 316-327.
Crossref
Rhydian Lewis, Kate Smith-Miles & Kyle Phillips. 2018. Combinatorial Algorithms. Combinatorial Algorithms 287 298 .
María Soto, Marc Sevaux, André Rossi & Andreas Reinholz. (2017) Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Computers & Industrial Engineering 107, pages 211-222.
Crossref
J. A. Morell & Enrique Alba. 2017. Smart Cities. Smart Cities 51 62 .
Kanjana Ruttanateerawichien, Werasak Kurutach & Tantikorn Pichpibul. (2016) A new efficient and effective golden-ball-based technique for the capacitated vehicle routing problem. A new efficient and effective golden-ball-based technique for the capacitated vehicle routing problem.
Johan Oppen. (2016) Decision Support for Flexible Liner Shipping. Advances in Operations Research 2016, pages 1-8.
Crossref
Eduardo Lalla-Ruiz, Christopher Expósito-Izquierdo, Shervin Taheripour & Stefan Voß. (2015) An improved formulation for the multi-depot open vehicle routing problem. OR Spectrum 38:1, pages 175-187.
Crossref
Wassila Aggoune‐Mtalaa, Zineb Habbas, Amine Ait Ouahmed & Djamel Khadraoui. (2015) Solving new urban freight distribution problems involving modular electric vehicles. IET Intelligent Transport Systems 9:6, pages 654-661.
Crossref
Rahma Lahyani, Mahdi Khemakhem & Frédéric Semet. (2015) Rich vehicle routing problems: From a taxonomy to a definition. European Journal of Operational Research 241:1, pages 1-14.
Crossref
Tantikorn Pichpibul. 2015. Industrial Engineering, Management Science and Applications 2015. Industrial Engineering, Management Science and Applications 2015 251 258 .
A.D. López-Sánchez, A.G. Hernández-Díaz, D. Vigo, R. Caballero & J. Molina. (2014) A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem. European Journal of Operational Research 238:1, pages 104-113.
Crossref
Jens Lysgaard & Sanne Wøhlk. (2014) A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. European Journal of Operational Research 236:3, pages 800-810.
Crossref
H.N. Nguyen, C.E. Rainwater, S.J. Mason & E.A. Pohl. (2014) Quantity discount with freight consolidation. Transportation Research Part E: Logistics and Transportation Review 66, pages 66-82.
Crossref
Ran Liu, Zhibin Jiang & Na Geng. (2012) A hybrid genetic algorithm for the multi-depot open vehicle routing problem. OR Spectrum 36:2, pages 401-421.
Crossref
Duygu Yilmaz Eroglu, Burcu Caglar Gencosman, Fatih Cavdur & H. Cenk Ozmutlu. (2014) Introducing the MCHF/OVRP/SDMP: Multicapacitated/Heterogeneous Fleet/Open Vehicle Routing Problems with Split Deliveries and Multiproducts. The Scientific World Journal 2014, pages 1-14.
Crossref
Kanjana Ruttanateerawichien, Werasak Kurutach & Tantikorn Pichpibul. 2014. Bio-Inspired Computing - Theories and Applications. Bio-Inspired Computing - Theories and Applications 341 356 .
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau & Christian Prins. (2013) Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research 231:1, pages 1-21.
Crossref
Tânia Rodrigues Pereira Ramos, Maria Isabel Gomes & Ana Paula Barbosa-Póvoa. (2013) Planning waste cooking oil collection systems. Waste Management 33:8, pages 1691-1703.
Crossref
Sandra Ulrich Ngueveu, Christian Prins & Roberto Wolfler Calvo. (2013) New Lower Bounds and Exact Method for the m -PVRP . Transportation Science 47:1, pages 38-52.
Crossref
Richard Y.K. Fung, Ran Liu & Zhibin Jiang. (2013) A memetic algorithm for the open capacitated arc routing problem. Transportation Research Part E: Logistics and Transportation Review 50, pages 53-67.
Crossref
Jorge Riera-Ledesma & Juan José Salazar-González. (2013) A column generation approach for a school bus routing problem with resource constraints. Computers & Operations Research 40:2, pages 566-583.
Crossref
Tantikorn Pichpibul & Ruengsak Kawtummachai. (2013) A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem. The Scientific World Journal 2013, pages 1-11.
Crossref
Glaydston Mattos Ribeiro, Guy Desaulniers & Jacques Desrosiers. (2012) A branch-price-and-cut algorithm for the workover rig routing problem. Computers & Operations Research 39:12, pages 3305-3315.
Crossref
Christophe Duhamel, Andréa Cynthia Santos & Lucas Moreira Guedes. (2012) Models and hybrid methods for the onshore wells maintenance problem. Computers & Operations Research 39:12, pages 2944-2953.
Crossref
Ran Liu & Zhibin Jiang. (2012) The close–open mixed vehicle routing problem. European Journal of Operational Research 220:2, pages 349-360.
Crossref
Glaydston Mattos Ribeiro, Gilbert Laporte & Geraldo Regis Mauri. (2012) A comparison of three metaheuristics for the workover rig routing problem. European Journal of Operational Research 220:1, pages 28-36.
Crossref
Jorge Riera-Ledesma & Juan-José Salazar-González. (2012) Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach. Computers & Operations Research 39:2, pages 391-404.
Crossref
S.A. MirHassani & N. Abolghasemi. (2011) A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications 38:9, pages 11547-11551.
Crossref
Farzaneh Daneshzand. 2011. Logistics Operations and Management. Logistics Operations and Management 127 153 .
Ran Liu, Zhibin Jiang, Hongtao Hu & Shiqing Yao. (2010) A memetic algorithm for the close-open mixed Vehicle Routing Problem. A memetic algorithm for the close-open mixed Vehicle Routing Problem.
Majid Salari, Paolo Toth & Andrea Tramontani. (2010) An ILP improvement procedure for the Open Vehicle Routing Problem. Computers & Operations Research 37:12, pages 2106-2120.
Crossref
Géraldine Heilporn, Jean-François Cordeau & Gilbert Laporte. (2010) The Delivery Man Problem with time windows. Discrete Optimization 7:4, pages 269-282.
Crossref
Sandra Ulrich Ngueveu, Christian Prins & Roberto Wolfler Calvo. (2010) An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Computers & Operations Research 37:11, pages 1877-1885.
Crossref
Jens Lysgaard. (2010) The pyramidal capacitated vehicle routing problem. European Journal of Operational Research 205:1, pages 59-64.
Crossref
Junhyuk Park & Byung-In Kim. (2010) The school bus routing problem: A review. European Journal of Operational Research 202:2, pages 311-319.
Crossref
Emmanouil E. Zachariadis & Chris T. Kiranoudis. (2010) An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Computers & Operations Research 37:4, pages 712-723.
Crossref
P.P. Repoussis, C.D. Tarantilis, O. Bräysy & G. Ioannou. (2010) A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research 37:3, pages 443-455.
Crossref
Visa Holopainen, Raimo Kantola, Taneli Taira & Olli-Pekka Lamminen. 2010. Mechanisms for Autonomous Management of Networks and Services. Mechanisms for Autonomous Management of Networks and Services 123 134 .
Artur Pessoa, Marcus Poggi de Aragão & Eduardo Uchoa. 2008. The Vehicle Routing Problem: Latest Advances and New Challenges. The Vehicle Routing Problem: Latest Advances and New Challenges 297 325 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.