Subgradient Methods for the Service Network Design Problem

Judith M. Farvolden and Warren B. Powell
Additional contact information
Judith M. Farvolden: Department of Industrial Engineering, University of Toronto, Toronto, Ontario, Canada M5S 1A4
Warren B. Powell: Department of Civil Engineering and Operations Research, Princeton University, Princeton, New Jersey 08544

Transportation Science, 1994, vol. 28, issue 3, 256-272

Abstract: We present local-improvement heuristics for a Service Network Design Problem encountered in the motor carrier industry. The scheduled set of vehicle departures determines the right hand side of the capacity constraints of the shipment routing subproblem which is modeled as a multicommodity network flow problem. The heuristics, one for dropping a scheduled service and another for introducing a new service, are based upon subgradients derived from the optimal dual variables of the shipment routing subproblem. The basis of the multicommodity network flow problem is partitioned to facilitate the calculation of the dual variables, reduced costs and subgradients. These are determined in large part by additive and network operations, and only in small part by matrix multiplication. The results of our computational experimentation are presented.

Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.28.3.256 (application/pdf)

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:inm:ortrsc:v:28:y:1994:i:3:p:256-272

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().