IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v50y2016i2p708-719.html

Solving the Single Vehicle Routing Problem with Variable Capacity

Author

Listed:
  • François V. Louveaux

    (Department of Business Administration, University of Namur, B-5000 Namur, Belgium)

  • Juan-José Salazar-González

    (DEIOC, University of La Laguna, 38271 Tenerife, Spain)

Abstract

This paper considers the classical vehicle routing problem (VRP) where the vehicle capacity is not fixed. Indeed, at the moment of acquiring (or renting) the vehicle that will serve all customers, there is some freedom of choice. A larger vehicle capacity implies a lower total distance travelled but larger operating costs. The reverse is true for a smaller vehicle. This paper gives an approach to select the best capacity and the best route to minimize a function of the acquisition cost and travelled distance.We first consider an enumerative approach, which consists of solving a sequence of VRPs, starting from the one having the largest capacity. The number of VRPs to solve using this approach is unknown. Based on computational experiments, this number is mostly large in our benchmark instances. We then proceed to a direct approach based on the two-index formulation of the VRP. We introduce several valid inequalities that allow us to have an integer linear programming formulation of the VRP with fixed vehicle capacity. We describe separation procedures for these inequalities. We conclude with computational results that confirm the utility of these inequalities when solving benchmark VRP instances.

Suggested Citation

  • François V. Louveaux & Juan-José Salazar-González, 2016. "Solving the Single Vehicle Routing Problem with Variable Capacity," Transportation Science, INFORMS, vol. 50(2), pages 708-719, May.
    • Handle: RePEc:inm:ortrsc:v:50:y:2016:i:2:p:708-719
    DOI: 10.1287/trsc.2014.0556
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2014.0556
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2014.0556?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. Mauro Dell'Amico & Manuel Iori & Silvano Martello & Michele Monaci, 2008. "Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 333-344, August.
    2. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
    3. 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.
    4. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    Full references (including those not matched with items on IDEAS)

    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. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    2. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt6zz2g0z4, University of California Transportation Center.
    3. Pan, Zhendong & Tang, Jiafu & Liu, Ou, 2009. "Capacitated dynamic lot sizing problems in closed-loop supply chain," European Journal of Operational Research, Elsevier, vol. 198(3), pages 810-821, November.
    4. Ventura, José A. & Valdebenito, Victor A. & Golany, Boaz, 2013. "A dynamic inventory model with supplier selection in a serial supply chain structure," European Journal of Operational Research, Elsevier, vol. 230(2), pages 258-271.
    5. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    6. Goisque, Guillaume & Rapine, Christophe, 2017. "An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels," European Journal of Operational Research, Elsevier, vol. 261(3), pages 918-928.
    7. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    8. van Hoesel, C.P.M. & Romeijn, H.E. & Romero Morales, M.D. & Wagelmans, A., 2002. "Polynomial time algorithms for some multi-level lot-sizing problems with production capacities," Research Memorandum 018, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    9. Bunn, Kevin A. & Ventura, José A., 2023. "A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs," European Journal of Operational Research, Elsevier, vol. 307(1), pages 116-129.
    10. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    11. Hong, Zhaofu & Chu, Chengbin & Yu, Yugang, 2016. "Dual-mode production planning for manufacturing with emission constraints," European Journal of Operational Research, Elsevier, vol. 251(1), pages 96-106.
    12. van Hoesel, C.P.M. & Wagelmans, A.P.M., 1997. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Econometric Institute Research Papers EI 9735/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    13. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    14. Önal, Mehmet & Romeijn, H.Edwin & Sapra, Amar & van den Heuvel, Wilco, 2015. "The economic lot-sizing problem with perishable items and consumption order preference," European Journal of Operational Research, Elsevier, vol. 244(3), pages 881-891.
    15. Hwang, Hark-Chin & Jaruphongsa, Wikrom, 2008. "Dynamic lot-sizing model for major and minor demands," European Journal of Operational Research, Elsevier, vol. 184(2), pages 711-724, January.
    16. van Hoesel, S. & Romeijn, H.E. & Romero Morales, D. & Wagelmans, A.P.M., 2002. "Polynomial Time Algorithms For Some Multi-Level Lot-Sizing Problems With Production Capacities," ERIM Report Series Research in Management ERS-2002-59-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    17. Akbalik, Ayse & Gicquel, Céline & Penz, Bernard & Rapine, Christophe, 2025. "Lot sizing with capacity adjustment using on-site green and grid electricity," Omega, Elsevier, vol. 133(C).
    18. Hoesel C.P.M. van & Wagelmans A.P.M., 1997. "Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    19. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    20. François Vanderbeck, 1998. "Lot-Sizing with Start-Up Times," Management Science, INFORMS, vol. 44(10), pages 1409-1425, October.

    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:ortrsc:v:50:y:2016:i:2:p:708-719. 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.