IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i4p987-1005.html

A Neural Separation Algorithm for the Rounded Capacity Inequalities

Author

Listed:
  • Hyeonah Kim

    (Department of Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea)

  • Jinkyoo Park

    (Department of Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; OMELET, Daejeon 34051, Republic of Korea)

  • Changhyun Kwon

    (Department of Industrial and Systems Engineering, KAIST, Daejeon 34141, Republic of Korea; OMELET, Daejeon 34051, Republic of Korea)

Abstract

The cutting plane method is a key technique for successful branch-and-cut and branch-price-and-cut algorithms that find the exact optimal solutions for various vehicle routing problems (VRPs). Among various cuts, the rounded capacity inequalities (RCIs) are the most fundamental. To generate RCIs, we need to solve the separation problem, whose exact solution takes a long time to obtain; therefore, heuristic methods are widely used. We design a learning-based separation heuristic algorithm with graph coarsening that learns the solutions of the exact separation problem with a graph neural network (GNN), which is trained with small instances of 50 to 100 customers. We embed our separation algorithm within the cutting plane method to find a lower bound for the capacitated VRP (CVRP) with up to 1,000 customers. We compare the performance of our approach with CVRPSEP, a popular separation software package for various cuts used in solving VRPs. Our computational results show that our approach finds better lower bounds than CVRPSEP for large-scale problems with 400 or more customers, whereas CVRPSEP shows strong competency for problems with less than 400 customers.

Suggested Citation

  • Hyeonah Kim & Jinkyoo Park & Changhyun Kwon, 2024. "A Neural Separation Algorithm for the Rounded Capacity Inequalities," INFORMS Journal on Computing, INFORMS, vol. 36(4), pages 987-1005, July.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:4:p:987-1005
    DOI: 10.1287/ijoc.2022.0310
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0310
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0310?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. Guy Desaulniers & Diego Pecin & Claudio Contardo, 2019. "Selective pricing in branch-price-and-cut algorithms for vehicle routing," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 147-168, June.
    3. Kate A. Smith, 1999. "Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 15-34, February.
    4. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    5. Gilbert Laporte & Yves Nobert & Martin Desrochers, 1985. "Optimal Routing under Capacity and Distance Restrictions," Operations Research, INFORMS, vol. 33(5), pages 1050-1073, October.
    6. Augerat, P. & Belenguer, J. M. & Benavent, E. & Corberan, A. & Naddef, D., 1998. "Separating capacity constraints in the CVRP using tabu search," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 546-557, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Caroline Spieckermann & Stefan Minner & Maximilian Schiffer, 2025. "Reduce-then-Optimize for the Fixed-Charge Transportation Problem," Transportation Science, INFORMS, vol. 59(3), pages 540-564, June.
    2. Abhay Sobhanan & Junyoung Park & Jinkyoo Park & Changhyun Kwon, 2025. "Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems," Transportation Science, INFORMS, vol. 59(2), pages 322-339, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yu Yang, 2023. "An Exact Price-Cut-and-Enumerate Method for the Capacitated Multitrip Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 57(1), pages 230-251, January.
    2. Roberto Baldacci & Paolo Toth & Daniele Vigo, 2010. "Exact algorithms for routing problems under vehicle capacity constraints," Annals of Operations Research, Springer, vol. 175(1), pages 213-245, March.
    3. David Applegate & William Cook & Sanjeeb Dash & André Rohe, 2002. "Solution of a Min-Max Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 132-143, May.
    4. Matteo Petris & Claudia Archetti & Diego Cattaruzza & Maxime Ogier & Frédéric Semet, 2025. "A tutorial on Branch-Price-and-Cut algorithms," 4OR, Springer, vol. 23(1), pages 1-52, March.
    5. Yang, Fei & Dai, Ying & Ma, Zu-Jun, 2020. "A cooperative rich vehicle routing problem in the last-mile logistics industry in rural areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    6. Clément Altman & Guy Desaulniers & Fausto Errico, 2023. "The Fragility-Constrained Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 57(2), pages 552-572, March.
    7. Zhenzhen Zhang & Yu Zhang & Roberto Baldacci, 2024. "Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework," Transportation Science, INFORMS, vol. 58(4), pages 761-780, July.
    8. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    9. Martinhon, Carlos & Lucena, Abilio & Maculan, Nelson, 2004. "Stronger K-tree relaxations for the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(1), pages 56-71, October.
    10. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    11. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    12. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    13. Daniel Yamín & Guy Desaulniers & Jorge E. Mendoza, 2025. "The Electric Vehicle Routing and Overnight Charging Scheduling Problem on a Multigraph," INFORMS Journal on Computing, INFORMS, vol. 37(4), pages 808-830, July.
    14. Liu, Tian & Luo, Zhixing & Qin, Hu & Lim, Andrew, 2018. "A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints," European Journal of Operational Research, Elsevier, vol. 266(2), pages 487-497.
    15. Kerscher, Christoph & Minner, Stefan, 2025. "Decompose-route-improve framework for solving large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).
    16. Archetti, C. & Coelho, L.C. & Speranza, M.G. & Vansteenwegen, P., 2026. "Beyond fifty years of vehicle routing: Insights into the history and the future," European Journal of Operational Research, Elsevier, vol. 330(2), pages 355-372.
    17. Faheng Deng & Hu Qin & Jiliu Li & Chun Cheng, 2023. "The Pickup and Delivery Problem with Time Windows and Incompatibility Constraints in Cold Chain Transportation," Transportation Science, INFORMS, vol. 57(2), pages 444-462, March.
    18. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    19. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    20. Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:36:y:2024:i:4:p:987-1005. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.