Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem

Lixing Yang and Xuesong Zhou

Transportation Research Part B: Methodological, 2014, vol. 59, issue C, 22-44

Abstract: Using a sample-based representation scheme to capture spatial and temporal travel time correlations, this article constructs an integer programming model for finding the a priori least expected time paths. We explicitly consider the non-anticipativity constraint associated with the a priori path in a time-dependent and stochastic network, and propose a number of reformulations to establish linear inequalities that can be easily dualized by a Lagrangian relaxation solution approach. The relaxed model is further decomposed into two sub-problems, which can be solved directly by using a modified label-correcting algorithm and a simple single-value linear programming method. Several solution algorithms, including a sub-gradient method, a branch and bound method, and heuristics with additional constraints on Lagrangian multipliers, are proposed to improve solution quality and find approximate optimal solutions. The numerical experiments investigate the quality and computational efficiency of the proposed solution approach.

Keywords: A priori least expected time path; Time-dependent traffic network; Lagrangian relaxation; Branch and bound algorithm (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261513001951
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:59:y:2014:i:c:p:22-44

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.2013.10.012

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 ().