International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 6, No. 2, 8 Apr. 2020
Cover page and Table of Contents: PDF (size: 160KB)
A Proposed Linear Programming Based Algorithm to Solve Arc Routing Problems
Full Text (PDF, 160KB), PP.61-70
Views: 0 Downloads: 0
Author(s)
Hashnayne Ahmed
1,*
Index Terms
Arc Routing Problem, Linear Programming, Proposed Algorithm, Travelling Salesperson Problem, Arc Routing with Uncertainty.
Abstract
A new linear programming-based algorithm has been demonstrated to find the best way for arc routing. In most arc routing problems, the main goal is to minimize the total cost on the lane. To find the minimum cost giving lane, the existing algorithms find the smallest possible sum of weights by ticking the shortest paths [7-12]. The proposed computer-based algorithm is based on focusing the minimized total cost with some constraint criteria of fixed values. The routes are marked with a series of variables that may differ according to the lane choice and more accurately estimates the exact total cost considering the remaining weight. Finally, a stochastic model for a private company vehicle transport has been discussed with some possible solution expectations.
Cite This Paper
Hashnayne Ahmed,"A Proposed Linear Programming Based Algorithm to Solve Arc Routing Problems", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.6, No.2, pp.61-70, 2020. DOI: 10.5815/ijmsc.2020.02.03
Reference
[1]Birge, John R., and Francois Louveaux. Introduction to stochastic programming. Springer Science & Business Media, 2011.
[2]Ahmed, Hashnayne. "Graph Routing Problem Using Euler’s Theorem and Its Applications." (2019).
[3]Eiselt, Horst A., Michel Gendreau, and Gilbert Laporte. "Arc routing problems, part II: The rural postman problem." Operations research 43.3 (1995): 399-414.
[4]Toth, Paolo, and Daniele Vigo, eds. Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics, 2014.
[5]Dror, Moshe, ed. Arc routing: theory, solutions, and applications. Springer Science & Business Media, 2012.
[6]Ahmed, Hashnayne. "Formulation of Two-Stage Stochastic Programming with Fixed Recourse." Britain International of Exact Sciences (BIoEx) Journal 1.1 (2019): 18-21.
[7]Prim, Robert Clay. "Shortest connection networks and some generalizations." The Bell System Technical Journal 36.6 (1957): 1389-1401.
[8]Kruskal, Joseph B. "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society 7.1 (1956): 48-50.
[9]Dijkstra, Edsger W. "A note on two problems in connexion with graphs." Numerische Mathematik 1.1 (1959): 269-271.
[10]Floyd, Robert W. "Algorithm 97: shortest path." Communications of the ACM 5.6 (1962): 345.
[11]Toth, Paolo, and Daniele Vigo. "An exact algorithm for the vehicle routing problem with backhauls." Transportation Science 31.4 (1997): 372-385.
[12]Guttoski, Pryscila Barvik, Marcos Sfair Sunye, and Fabiano Silva. "Kruskal's algorithm for query tree optimization." 11th International Database Engineering and Applications Symposium (IDEAS 2007). IEEE, 2007.
[13]Assad, Arjang A., and Bruce L. Golden. "Arc routing methods and applications." Handbooks in operations research and management science 8 (1995): 375-483.
[14]Tirkolaee, Erfan Babaee, et al. "An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem." Computers & Electrical Engineering 77 (2019): 457-470.
[15]Lacomme, Philippe, Christian Prins, and Wahiba Ramdane-Cherif. "Competitive memetic algorithms for arc routing problems." Annals of Operations Research 131.1-4 (2004): 159-185.
[16]Campbell, James F., et al. "Drone arc routing problems." Networks 72.4 (2018): 543-559.
[17]Poikonen, Stefan, Xingyin Wang, and Bruce Golden. "The vehicle routing problem with drones: Extended models and connections." Networks 70.1 (2017): 34-43.