iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s11590-023-02082-w
An improved model for estimating optimal VRP solution values | Optimization Letters Skip to main content

Advertisement

Springer Nature Link
Log in

An improved model for estimating optimal VRP solution values

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Since it is computationally expensive to solve the vehicle routing problem (VRP) optimally, as this problem is NP-hard, in this technical note we study how to accurately approximate the optimal VRP tour length. In our previous papers, we developed a linear regression model including the mean and standard deviation of the modified Clarke and Wright heuristic solution values, which was able to predict the optimal VRP tour length fairly well. In this note, we find that by doing a small amount of extra work to include the minimum of the modified Clarke and Wright heuristic solution values, we can improve the predictive results substantially.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Data availability

The datasets generated during and/or analysed as part of the current study are available from the corresponding author upon request.

References

  1. Akkerman, F., Mes, M.: Distance approximation to support customer selection in vehicle routing problems. Ann. Oper. Res., pp. 1–29 (2022)

  2. Basel, J., Willemain, T.R.: Random tours in the traveling salesman problem: analysis and application. Comput. Opt. Appl. 20(2), 211–217 (2001)

    Article  MathSciNet  Google Scholar 

  3. Christofides, N., Mingozzi, A., Toth, P.: The Vehicle Routing Problem. Combinatorial Optimization. John Wiley and Sons, London (1979)

    Google Scholar 

  4. Daganzo, C.F.: The distance traveled to visit n points with a maximum of c stops per vehicle: an analytic model and an application. Transp. Sci. 18(4), 331–350 (1984)

    Article  MathSciNet  Google Scholar 

  5. Figliozzi, M.A.: Planning approximations to the average length of vehicle routing problems with varying customer demands and routing constraints. Transp. Res. Record 2089(1), 1–8 (2008)

    Article  Google Scholar 

  6. Kou, S., Golden, B., Poikonen, S.: Optimal TSP tour length estimation using standard deviation as a predictor. Comput. Oper. Res. 148, 105993 (2022)

    Article  MathSciNet  Google Scholar 

  7. Kou, S., Golden, B., Poikonen, S.: Estimating optimal objective values for the TSP, VRP, and other combinatorial problems using randomization. Int. Trans. Oper. Res. (2023)

  8. Queiroga, E., Sadykov, R., Uchoa, E., & Vidal, T. (2021). 10,000 Optimal CVRP solutions for testing machine learning based heuristics. In: AAAI-22 workshop on machine learning for operations research (ML4OR)

  9. Robust, F., Daganzo, C.F., Souleyrette, R.R., II.: Implementing vehicle routing models. Transp. Res. Part B Methodol. 24(4), 263–286 (1990)

    Article  Google Scholar 

  10. Sinha Roy, D., Golden, B., Masone, A., Wasil, E.: Using regression models to understand the impact of route-length variability in practical vehicle routing. Opt. Lett. 17(1), 163–175 (2023)

    Article  MathSciNet  Google Scholar 

  11. Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., Subramanian, A.: New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3), 845–858 (2017)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Maryland, College Park, MD, USA

    Shuhan Kou

  2. Robert H. Smith School of Business, University of Maryland, College Park, MD, USA

    Bruce Golden

  3. Department of Economics and Management, University of Brescia, Brescia, Italy

    Luca Bertazzi

Authors
  1. Shuhan Kou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bruce Golden
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luca Bertazzi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shuhan Kou.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kou, S., Golden, B. & Bertazzi, L. An improved model for estimating optimal VRP solution values. Optim Lett 18, 697–703 (2024). https://doi.org/10.1007/s11590-023-02082-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-023-02082-w

Keywords

Search

Navigation