Open AccessThe multi-point delivery problem: Shortest Path Algorithm for Real Roads Network using Dijkstra
Author(s) -
Samaher Adnan,
enas Wahab Abood,
Wafaa Abdulmuhsin
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1530/1/012040
Subject(s) - shortest path problem , dijkstra's algorithm , constrained shortest path first , computer science , path (computing) , yen's algorithm , start point , point (geometry) , k shortest path routing , algorithm , mathematical optimization , vehicle routing problem , graph , routing (electronic design automation) , mathematics , real time computing , end point , theoretical computer science , computer network , geometry
The Multi-point Delivery problem is a Vehicle Routing problem (VRP) in which the vehicle has single point as start and end point and must visit a set of points as customers to replay their requests. This paper produces an algorithm built for finding a shortest path for multi-points delivery problem can be used by drivers and autonomous vehicle. The system uses a real road map for a part of Altijari center of Basrah as a delivery problem. The process is firstly built a proper graph to represent the roads then used Dijkstra Shortest Path algorithm to find the shortest path from start point to all points need to be served then taking the closest one and considered as new start point, continue researching to find short path to other points until all points visited, that for forward path, thus each point path is added to get the full path that pass in all points in delivery scope to get an optimize arrangement for visiting required points with least cost. The second step is to calculate the path for backward to start point. The experimental results show that the proposed algorithm performed efficiently in terms of cost for paths and time for calculation.