[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Vehicle routing problem with uniform private fleet and common carrier: a node subset heuristic

  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

Abstract

Optimizing the distribution of goods to customers is discussed on non-split delivery modification of vehicle routing problem with uniform private fleet and common carrier. While private fleet costs are proportional to the sum of distances traveled by its vehicles, common carrier has no capacity limit and costs are proportional to the quantity of transported goods only. We show the transformation of the model onto the vehicle routing problem with optional enter and propose a modified insert heuristic. The main contribution is a node subset heuristic based on dividing nodes into two subsets. The heuristic uses the node pre-selection for the private fleet while the rest is served by the common carrier. In the second step, both subsets are solved separately. The performance of the integer linear program and both proposed heuristics are compared on testing instances. Both heuristics can be used for finding the initial solution which can be further improved by local search methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Auer P, Dósa G, Dulai T, Fügenschuh A, Näser P, Ortner R, Werner-Stark Á (2020) A new heuristic and an exact approach for a production planning problem. Central European Journal of Operations Research pp 1–35

  • Belenguer JM, Benavent E, Lacomme P, Prins C (2006) Lower and upper bounds for the mixed capacitated arc routing problem. Computers & Oper Res 33(12):3363–3383

    Article  Google Scholar 

  • Bolduc MC, Renaud J, Boctor F (2007) A heuristic for the routing and carrier selection problem. Eur J Oper Res 183:926–932. https://doi.org/10.1016/j.ejor.2006.10.013

    Article  Google Scholar 

  • Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: State of the art classification and review. Computers & Ind Eng 99:300–313

    Article  Google Scholar 

  • Chu CW (2005) A heuristic algorithm for the truckload and less-than-truckload problem. Eur J Oper Res 165(3):657–667

    Article  Google Scholar 

  • Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581

    Article  Google Scholar 

  • Côté JF, Potvin JY (2009) A tabu search heuristic for the vehicle routing problem with private fleet and common carrier. Eur J Oper Res 198(2):464–469

    Article  Google Scholar 

  • Dabia S, Lai D, Vigo D (2019) An exact algorithm for a rich vehicle routing problem with private fleet and common carrier. Transp Sci 53(4):986–1000

    Article  Google Scholar 

  • Das SK, Roy SK, Weber GW (2020) Heuristic approaches for solid transportation-p-facility location problem. Cent Eur J Oper Res 28(3):939–961

    Article  Google Scholar 

  • Eksioglu B, Vural AV, Reisman A (2009) The vehicle routing problem: a taxonomic review. Computers & Ind Eng 57(4):1472–1483

    Article  Google Scholar 

  • El-Sherbeny NA (2010) Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods. J King Saud Univ-Sci 22(3):123–131

    Article  Google Scholar 

  • Euchi J (2017) The vehicle routing problem with private fleet and multiple common carriers: solution with hybrid metaheuristic algorithm. Vehicular Commun 9:97–108

    Article  Google Scholar 

  • Euchi J, Chabchoub H (2011) Hybrid metaheuristics for the profitable arc tour problem. J Oper Res Soc 62(11):2013–2022

    Article  Google Scholar 

  • Pelikán J (2016) Heuristics for VRP with Private and Common Carriers. In: 34th International Conference Mathematical Methods in Economics (MME 2016), Technical University Liberec, pp 658–662, 34th International Conference Mathematical Methods in Economics (MME), Liberec, Czech Republic, September 06-09, 2016

  • Pelikán J (2018) Vehicle Routing Problem with External Carrier. In: 461 Hradec Economic Days 2018, Hradec Economic Days, vol 8, pp127–132, 16th International Scientific 462 Conference on Hradec Economic Days, Hradec Kralove, Czech Republic, January 30–31, 2018

  • Plevný M (2013) Vehicle routing problem with a private fleet and common carriers - the variety with a possibility of sharing the satisfaction of demand. In: Mathematical Methods in Economy 2013, pp 730–736, 31st International Conference on Mathematical Methods in Economics, Jihlava, Czech Republic, September 11–13, 2013

  • Potvin JY, Naud MA (2011) Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier. J Oper Res Soc 62(2):326–336

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Petr Štourač.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work was supported by the Czech Science Foundation under grant 19-02773S and by the Internal Grant Agency of Prague University of Economics and Business under Grant F4/19/2019.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pelikán, J., Štourač, P. & Sokol, O. Vehicle routing problem with uniform private fleet and common carrier: a node subset heuristic. Cent Eur J Oper Res 30, 683–697 (2022). https://doi.org/10.1007/s10100-021-00759-0

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-021-00759-0

Keywords

Navigation