EconPapers    
Economics at your fingertips  
 

Parametric search for the bi-attribute concave shortest path problem

Yuli Zhang, Zuo-Jun Max Shen and Shiji Song

Transportation Research Part B: Methodological, 2016, vol. 94, issue C, 150-168

Abstract: A bi-attribute concave shortest path (BC-SP) problem seeks to find an optimal path in a bi-attribute network that minimizes a linear combination of two path costs, one of which is evaluated by a nondecreasing concave function. Due to the nonadditivity of its objective function, Bellman’s principle of optimality does not hold. This paper proposes a parametric search method to solve the BC-SP problem, which only needs to solve a series of shortest path problems, i.e., the parameterized subproblems (PSPs). Several techniques are developed to reduce both the number of PSPs and the computation time for these PSPs. Specifically, we first identify two properties of the BC-SP problem to guide the parametric search using the gradient and concavity of its objective function. Based on the properties, a monotonic descent search (MDS) and an intersection point search (IPS) are proposed. Second, we design a speedup label correcting (LC) algorithm, which uses optimal solutions of previously solved PSPs to reduce the number of labeling operations for subsequent PSPs. The MDS, IPS and speedup LC techniques are embedded into a branch-and-bound based interval search to guarantee optimality. The performance of the proposed method is tested on the mean-standard deviation shortest path problem and the route choice problem with a quadratic disutility function. Experiments on both real transportation networks and grid networks show that the proposed method reduces the computation time of existing algorithms by one to two orders of magnitude.

Keywords: Bi-attribute concave shortest path; Parametric search; Interval search; Speedup label correcting (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4) Track citations by RSS feed

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516303848
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:94:y:2016:i:c:p:150-168

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2016.09.009

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).

 
Page updated 2024-02-12
Handle: RePEc:eee:transb:v:94:y:2016:i:c:p:150-168