An efficient algorithm for solving the median problem on real road networks. Issue 6 (2nd June 2020)

• Record Type: Journal Article
• Authors: Ghanbartehrani, Saeed; Porter, J. David
• Is Part Of: Engineering optimization. Volume 52:Issue 6(2020)
• Page Start: 973
• Page End: 986
• Publication Date: 2020-06-02
• Subjects: Median problem -- network location -- multi-threaded Dijkstra's algorithm -- real road networks; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2019.1631305
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: The objective of the median problem is to optimize the location of a facility so that the sum of demand-weighted distances from a set of demand points is minimized. In this article, an algorithm for solving the median problem on real road networks is proposed. The proposed algorithm, referred to as multi-threaded Dijkstra's (MTD), works with very large road networks, does not require computationally intensive pre-processing of the network data and offers reasonable runtime. The MTD algorithm is used to evaluate several facility location scenarios on various road networks with 2000–50, 000 nodes. Solutions are compared against an exhaustive search. The results show that the MTD algorithm is capable of solving median problems on very large networks and its runtime is influenced by factors such as the number of demand points, network size and size of the area in which the demand points are distributed.