Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems
The vehicle routing problem (VRP) attempts to find optimal (minimum length) routes for a set of vehicles visiting a set of locations. Solving a VRP calls for a cost matrix between locations. The size of the matrix grows quadratically with an increasing number of locations, restricting large-sized VR...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-02-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2220-9964/12/2/57 |
| _version_ | 1797620581044060160 |
|---|---|
| author | Keyju Lee Junjae Chae |
| author_facet | Keyju Lee Junjae Chae |
| author_sort | Keyju Lee |
| collection | DOAJ |
| description | The vehicle routing problem (VRP) attempts to find optimal (minimum length) routes for a set of vehicles visiting a set of locations. Solving a VRP calls for a cost matrix between locations. The size of the matrix grows quadratically with an increasing number of locations, restricting large-sized VRPs from being solved in a reasonable amount of time. The time needed to obtain a cost matrix is expensive when routing engines are used, which solve shortest path problems in the back end. In fact, details on the shortest path are redundant; only distance or time values are necessary for VRPs. In this study, an artificial neural network (ANN) that receives two geo-coordinates as input and provides estimated cost (distance and time) as output is trained. The trained ANN model was able to estimate with a mean absolute percentage error of 7.68%, surpassing the quality of 13.2% with a simple regression model on Euclidean distance. The possibility of using a trained model in VRPs is examined with different implementation scenarios. The experimental results with VRPs confirm that using ANN estimation instead of Euclidean distance produces a better solution, which is verified to be statistically significant. The results also suggest that an ANN can be a better choice than routing engines when the trade-off between response time and solution quality is considered. |
| first_indexed | 2024-03-11T08:44:37Z |
| format | Article |
| id | doaj.art-11e5fa7be98446b6a2d52b6d6c6f1017 |
| institution | Directory Open Access Journal |
| issn | 2220-9964 |
| language | English |
| last_indexed | 2024-03-11T08:44:37Z |
| publishDate | 2023-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj.art-11e5fa7be98446b6a2d52b6d6c6f10172023-11-16T20:54:19ZengMDPI AGISPRS International Journal of Geo-Information2220-99642023-02-011225710.3390/ijgi12020057Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing ProblemsKeyju Lee0Junjae Chae1School of Air Transport, Transportation and Logistics, Korea Aerospace University, Goyang 10540, Gyeonggi-do, Republic of KoreaSchool of Air Transport, Transportation and Logistics, Korea Aerospace University, Goyang 10540, Gyeonggi-do, Republic of KoreaThe vehicle routing problem (VRP) attempts to find optimal (minimum length) routes for a set of vehicles visiting a set of locations. Solving a VRP calls for a cost matrix between locations. The size of the matrix grows quadratically with an increasing number of locations, restricting large-sized VRPs from being solved in a reasonable amount of time. The time needed to obtain a cost matrix is expensive when routing engines are used, which solve shortest path problems in the back end. In fact, details on the shortest path are redundant; only distance or time values are necessary for VRPs. In this study, an artificial neural network (ANN) that receives two geo-coordinates as input and provides estimated cost (distance and time) as output is trained. The trained ANN model was able to estimate with a mean absolute percentage error of 7.68%, surpassing the quality of 13.2% with a simple regression model on Euclidean distance. The possibility of using a trained model in VRPs is examined with different implementation scenarios. The experimental results with VRPs confirm that using ANN estimation instead of Euclidean distance produces a better solution, which is verified to be statistically significant. The results also suggest that an ANN can be a better choice than routing engines when the trade-off between response time and solution quality is considered.https://www.mdpi.com/2220-9964/12/2/57travel time predictiontravel cost estimationartificial neural networkvehicle routing problem |
| spellingShingle | Keyju Lee Junjae Chae Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems ISPRS International Journal of Geo-Information travel time prediction travel cost estimation artificial neural network vehicle routing problem |
| title | Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems |
| title_full | Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems |
| title_fullStr | Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems |
| title_full_unstemmed | Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems |
| title_short | Estimation of Travel Cost between Geographic Coordinates Using Artificial Neural Network: Potential Application in Vehicle Routing Problems |
| title_sort | estimation of travel cost between geographic coordinates using artificial neural network potential application in vehicle routing problems |
| topic | travel time prediction travel cost estimation artificial neural network vehicle routing problem |
| url | https://www.mdpi.com/2220-9964/12/2/57 |
| work_keys_str_mv | AT keyjulee estimationoftravelcostbetweengeographiccoordinatesusingartificialneuralnetworkpotentialapplicationinvehicleroutingproblems AT junjaechae estimationoftravelcostbetweengeographiccoordinatesusingartificialneuralnetworkpotentialapplicationinvehicleroutingproblems |