Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem

James Riechel

doi:doi:10.11648/j.ijtet.20210704.12

| Peer-Reviewed

Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem

James Riechel

Published in International Journal of Transportation Engineering and Technology (Volume 7, Issue 4)

Received: 21 October 2021 Accepted: 8 November 2021 Published: 17 November 2021

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

A solution to the vehicle routing problem (VRP) is presented that takes only quadratic space, O(n²), and quadratic time, O(n²), if n is the number of stops on a route. The input is assumed to be a list of stops of length n in longitude, latitude format. The output is an origin-destination (OD) matrix of size O(n²), which takes O(n²) time to build. The element (i, j) in the matrix is the approximate driving distance between stop i and stop j on the route. Each approximate driving distance takes constant or O(1) time to compute. (The approximate driving distance appears in previous work by the author, published in URISA GIS-Pro ‘19 and CalGIS 2020.) This OD matrix is well-suited for solving large-scale and very large-scale VRP problems, since computing approximate driving distances is lightning fast. For instance, using real-world data, it took less than one (1) second to produce a route with 5,156 stops. The OD matrix can be used with any exact or approximation algorithm to find a route, including the nearest-neighbor approximation algorithm: Starting at an origin, the next closest stop is visited repeatedly, ending at the destination once all stops have been visited. Determining the next stop to visit takes linear or O(n) time to compute, and this is done O(n) times. This solution to the VRP is a polynomial-time, O(n²), approximation; it is not exact, but is extremely fast.

Published in	International Journal of Transportation Engineering and Technology (Volume 7, Issue 4)
DOI	10.11648/j.ijtet.20210704.12
Page(s)	97-103
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2021. Published by Science Publishing Group

Keywords

Vehicle Routing Problem (VRP), Approximate Driving Distance, Manhattan Distance, Equirectangular Projection, Nearest-neighbor Approximation Algorithm

References

[1]	Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6 (1), 80–91. https://doi.org/10.1287/mnsc.6.1.80
[2]	Figliozzi, M. (2010). Vehicle Routing Problem for Emissions Minimization. Transportation Research Record: Journal of the Transportation Research Board, 2197 (1), 1–7. https://doi.org/10.3141/2197-01
[3]	Hargitai, H., Willner, K., & Hare, T. (2019). Fundamental Frameworks in Planetary Mapping: A Review. In H. Hargitai (Ed.), Planetary Cartography and GIS (pp. 75–101). Springer International Publishing. https://doi.org/10.1007/978-3-319-62849-3_4
[4]	Karp, R. M. (1972). Reducibility among Combinatorial Problems. In R. E. Miller, J. W. Thatcher, & J. D. Bohlinger (Eds.), Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9
[5]	Lenstra, J. K., & Kan, A. H. G. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11 (2), 221–227. https://doi.org/10.1002/net.3230110211
[6]	Li, S., Dragicevic, S., Castro, F. A., Sester, M., Winter, S., Coltekin, A., Pettit, C., Jiang, B., Haworth, J., Stein, A., & Cheng, T. (2016). Geospatial big data handling theory and methods: A review and research challenges. ISPRS Journal of Photogrammetry and Remote Sensing, 115, 119–133. https://doi.org/10.1016/j.isprsjprs.2015.10.012
[7]	Papadimitriou, C. H. (1977). The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science, 4 (3), 237–244. https://doi.org/10.1016/0304-3975(77)90012-3
[8]	Riechel, J. (2019). A fast algorithm for computing approximate distances in the Cartesian plane. Proceedings of URISA GIS-Pro ‘19, New Orleans, LA. https://urisa.library.esri.com/cgi-bin/koha/opac-detail.pl?biblionumber=183148&query_desc=kw%2Cwrdl%3A%20riechel
[9]	Riechel, J. (2020a). Comparing Manhattan, Euclidean, and Actual Driving Distances. Proceedings of CalGIS 2020, Long Beach, CA. https://drive.google.com/file/d/1_wgjePJH6LXM6OAYHg-PJkr2o-wVr8AK/view?usp=sharing
[10]	Riechel, J. (2020b). Extending Manhattan, Euclidean, and Actual Driving Distances into 3D. Unpublished. https://drive.google.com/file/d/16rkw9Ysn8BWfT7CpfvlnlaSwUgBw4Y4v/view?usp=sharing
[11]	Ripplinger, D. (1922). Rural School Vehicle Routing Problem. Transportation Research Record, 6.
[12]	Rosenkrantz, D. J., Stearns, R. E., & Lewis, I., Philip M. (1977). An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing, 6 (3), 563–581. https://doi.org/10.1137/0206041
[13]	Singh, A., Yadav, A., Block, A. E., Rana, A., Block, E., & Floor, G. (2013). K-means with Three different Distance Metrics. International Journal of Computer Applications, 67 (10), 13–17. https://doi.org/doi:10.5120/11430-6785
[14]	Tang, H., & Miller-Hooks, E. (1964). Interactive Heuristic for Practical Vehicle Routing Problem with Solution Shape Constraints. Transportation Research Record, 10.
[15]	Wang, Y., Ma, X., Lao, Y., Wang, Y., & Mao, H. (2013). Vehicle Routing Problem: Simultaneous Deliveries and Pickups with Split Loads and Time Windows. Transportation Research Record: Journal of the Transportation Research Board, 2378 (1), 120–128. https://doi.org/10.3141/2378-13
[16]	Zeager, J., & Stitz, C. (2016). College Algebra. http://dspace.calstate.edu/handle/10211.3/180387

Cite This Article

Plain Text BibTeX RIS

APA Style

James Riechel. (2021). Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem. International Journal of Transportation Engineering and Technology, 7(4), 97-103. https://doi.org/10.11648/j.ijtet.20210704.12

Copy | Download

ACS Style

James Riechel. Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem. Int. J. Transp. Eng. Technol. 2021, 7(4), 97-103. doi: 10.11648/j.ijtet.20210704.12

Copy | Download

AMA Style

James Riechel. Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem. Int J Transp Eng Technol. 2021;7(4):97-103. doi: 10.11648/j.ijtet.20210704.12

Copy | Download

@article{10.11648/j.ijtet.20210704.12,
  author = {James Riechel},
  title = {Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem},
  journal = {International Journal of Transportation Engineering and Technology},
  volume = {7},
  number = {4},
  pages = {97-103},
  doi = {10.11648/j.ijtet.20210704.12},
  url = {https://doi.org/10.11648/j.ijtet.20210704.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtet.20210704.12},
  abstract = {A solution to the vehicle routing problem (VRP) is presented that takes only quadratic space, O(n2), and quadratic time, O(n2), if n is the number of stops on a route. The input is assumed to be a list of stops of length n in longitude, latitude format. The output is an origin-destination (OD) matrix of size O(n2), which takes O(n2) time to build. The element (i, j) in the matrix is the approximate driving distance between stop i and stop j on the route. Each approximate driving distance takes constant or O(1) time to compute. (The approximate driving distance appears in previous work by the author, published in URISA GIS-Pro ‘19 and CalGIS 2020.) This OD matrix is well-suited for solving large-scale and very large-scale VRP problems, since computing approximate driving distances is lightning fast. For instance, using real-world data, it took less than one (1) second to produce a route with 5,156 stops. The OD matrix can be used with any exact or approximation algorithm to find a route, including the nearest-neighbor approximation algorithm: Starting at an origin, the next closest stop is visited repeatedly, ending at the destination once all stops have been visited. Determining the next stop to visit takes linear or O(n) time to compute, and this is done O(n) times. This solution to the VRP is a polynomial-time, O(n2), approximation; it is not exact, but is extremely fast.},
 year = {2021}
}

Copy | Download

TY  - JOUR
T1  - Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem
AU  - James Riechel
Y1  - 2021/11/17
PY  - 2021
N1  - https://doi.org/10.11648/j.ijtet.20210704.12
DO  - 10.11648/j.ijtet.20210704.12
T2  - International Journal of Transportation Engineering and Technology
JF  - International Journal of Transportation Engineering and Technology
JO  - International Journal of Transportation Engineering and Technology
SP  - 97
EP  - 103
PB  - Science Publishing Group
SN  - 2575-1751
UR  - https://doi.org/10.11648/j.ijtet.20210704.12
AB  - A solution to the vehicle routing problem (VRP) is presented that takes only quadratic space, O(n2), and quadratic time, O(n2), if n is the number of stops on a route. The input is assumed to be a list of stops of length n in longitude, latitude format. The output is an origin-destination (OD) matrix of size O(n2), which takes O(n2) time to build. The element (i, j) in the matrix is the approximate driving distance between stop i and stop j on the route. Each approximate driving distance takes constant or O(1) time to compute. (The approximate driving distance appears in previous work by the author, published in URISA GIS-Pro ‘19 and CalGIS 2020.) This OD matrix is well-suited for solving large-scale and very large-scale VRP problems, since computing approximate driving distances is lightning fast. For instance, using real-world data, it took less than one (1) second to produce a route with 5,156 stops. The OD matrix can be used with any exact or approximation algorithm to find a route, including the nearest-neighbor approximation algorithm: Starting at an origin, the next closest stop is visited repeatedly, ending at the destination once all stops have been visited. Determining the next stop to visit takes linear or O(n) time to compute, and this is done O(n) times. This solution to the VRP is a polynomial-time, O(n2), approximation; it is not exact, but is extremely fast.
VL  - 7
IS  - 4
ER  -

Copy | Download

Author Information

James Riechel

Center for Information Systems & Technology (CISAT), Claremont Graduate University (CGU), Claremont, the United States

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

James Riechel. (2021). Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem. International Journal of Transportation Engineering and Technology, 7(4), 97-103. https://doi.org/10.11648/j.ijtet.20210704.12

Copy | Download

ACS Style

James Riechel. Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem. Int. J. Transp. Eng. Technol. 2021, 7(4), 97-103. doi: 10.11648/j.ijtet.20210704.12

Copy | Download

AMA Style

James Riechel. Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem. Int J Transp Eng Technol. 2021;7(4):97-103. doi: 10.11648/j.ijtet.20210704.12

Copy | Download

@article{10.11648/j.ijtet.20210704.12,
  author = {James Riechel},
  title = {Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem},
  journal = {International Journal of Transportation Engineering and Technology},
  volume = {7},
  number = {4},
  pages = {97-103},
  doi = {10.11648/j.ijtet.20210704.12},
  url = {https://doi.org/10.11648/j.ijtet.20210704.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtet.20210704.12},
  abstract = {A solution to the vehicle routing problem (VRP) is presented that takes only quadratic space, O(n2), and quadratic time, O(n2), if n is the number of stops on a route. The input is assumed to be a list of stops of length n in longitude, latitude format. The output is an origin-destination (OD) matrix of size O(n2), which takes O(n2) time to build. The element (i, j) in the matrix is the approximate driving distance between stop i and stop j on the route. Each approximate driving distance takes constant or O(1) time to compute. (The approximate driving distance appears in previous work by the author, published in URISA GIS-Pro ‘19 and CalGIS 2020.) This OD matrix is well-suited for solving large-scale and very large-scale VRP problems, since computing approximate driving distances is lightning fast. For instance, using real-world data, it took less than one (1) second to produce a route with 5,156 stops. The OD matrix can be used with any exact or approximation algorithm to find a route, including the nearest-neighbor approximation algorithm: Starting at an origin, the next closest stop is visited repeatedly, ending at the destination once all stops have been visited. Determining the next stop to visit takes linear or O(n) time to compute, and this is done O(n) times. This solution to the VRP is a polynomial-time, O(n2), approximation; it is not exact, but is extremely fast.},
 year = {2021}
}

Copy | Download

TY  - JOUR
T1  - Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem
AU  - James Riechel
Y1  - 2021/11/17
PY  - 2021
N1  - https://doi.org/10.11648/j.ijtet.20210704.12
DO  - 10.11648/j.ijtet.20210704.12
T2  - International Journal of Transportation Engineering and Technology
JF  - International Journal of Transportation Engineering and Technology
JO  - International Journal of Transportation Engineering and Technology
SP  - 97
EP  - 103
PB  - Science Publishing Group
SN  - 2575-1751
UR  - https://doi.org/10.11648/j.ijtet.20210704.12
AB  - A solution to the vehicle routing problem (VRP) is presented that takes only quadratic space, O(n2), and quadratic time, O(n2), if n is the number of stops on a route. The input is assumed to be a list of stops of length n in longitude, latitude format. The output is an origin-destination (OD) matrix of size O(n2), which takes O(n2) time to build. The element (i, j) in the matrix is the approximate driving distance between stop i and stop j on the route. Each approximate driving distance takes constant or O(1) time to compute. (The approximate driving distance appears in previous work by the author, published in URISA GIS-Pro ‘19 and CalGIS 2020.) This OD matrix is well-suited for solving large-scale and very large-scale VRP problems, since computing approximate driving distances is lightning fast. For instance, using real-world data, it took less than one (1) second to produce a route with 5,156 stops. The OD matrix can be used with any exact or approximation algorithm to find a route, including the nearest-neighbor approximation algorithm: Starting at an origin, the next closest stop is visited repeatedly, ending at the destination once all stops have been visited. Determining the next stop to visit takes linear or O(n) time to compute, and this is done O(n) times. This solution to the VRP is a polynomial-time, O(n2), approximation; it is not exact, but is extremely fast.
VL  - 7
IS  - 4
ER  -

Copy | Download