An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays.

*(English)*Zbl 0967.90009Summary: The authors present a time-dependent intermodal optimum path algorithm for multimodal transportation networks that accounts for delays at mode and arc switching points. The correctness and computational complexity of the algorithm are proved. A simple representation of the mode-to-mode switching options is introduced that results in a substantially improved design, with computational complexity independent of the number of modes and fixed schedule lines for typical transit and freight networks. The algorithm is implemented, coded, and computationally tested on realistic size networks with promising results.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90B10 | Deterministic network models in operations research |

90C60 | Abstract computational complexity for mathematical programming problems |

##### Keywords:

shortest path algorithms; freight transportation; multimodal transportation networks; correctness; computational complexity; mode-to-mode switching
PDF
BibTeX
XML
Cite

\textit{A. Ziliaskopoulos} and \textit{W. Wardell}, Eur. J. Oper. Res. 125, No. 3, 486--502 (2000; Zbl 0967.90009)

Full Text:
DOI

##### References:

[1] | Aho, A.; Hopcroft, J.; Ullman, J., Data structures and algorithms, (1983), Addison-Wesley Reading, MA |

[2] | M. Battista, M. Lucertini, B. Simeone, Path composition and multiple choice in bimodal transportation network, in: Proceedings of the Seventh WCTR, Sydney, Australia, 1995 |

[3] | Bellman, R., On a routing problem, Quarterly of applied mathematics, 16, 87-90, (1958) · Zbl 0081.14403 |

[4] | Crainic, T.; Rousseau, J.M., Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem, Transportation research. part B, 20, 225-242, (1986) |

[5] | R.B. Dial, G.S. Rutherford, L. Quillian, Transit Network Analysis: INET, DOT, UMTA, Springfield, VA, 1979 |

[6] | Florian, M., A traffic equilibrium model of travel by car and public transit modes, Transportation science, 11, 166-179, (1977) |

[7] | S. Nguyen, S. Pallotino, F. Malucelli, A modeling framework for the passenger assignment on a transport network with time-tables, CRT-94-47 University of Montreal, Quebec, CA, 1995 |

[8] | Pallotino, S., Shortest-path methods: complexity, interrelations and new propositions, Networks, 14, 257-267, (1984) · Zbl 0583.90103 |

[9] | Spiess, H.; Florian, M., Optimal strategies: A new assignment model for transit networks, Transportation research. part B, 23, 83-102, (1989) |

[10] | A.K. Ziliaskopoulos, Optimum path algorithms on multidimensional networks: Analysis, design, implementation and computational experience, Ph.D. Dissertation, The University of Texas at Austin, Austin, TX, 1994 |

[11] | Ziliaskopoulos, A.K.; Mahmassani, H.S., A time-dependent shortest path algorithm for real-time intelligent vehicle/highway systems, Transportation research record, 1408, 94-104, (1993) |

[12] | A.K. Ziliaskopoulos, H.S. Mahmassani, Design and implementation of time-dependent optimum path algorithms, Operations Research (1997), under revision |

[13] | Ziliaskopoulos, A.K.; Mahmassani, H.S., On finding least time paths considering delays for intersection movements, Transportation research. part B, 30, 5, 359-370, (1996) |

[14] | National Commission on Intermodal Transportation, Toward a National Intermodal Transportation System, Final Report to Congress, US DOT, Washington, DC, 1994 |

[15] | G. Rawlings, One System, Many Partners: Reflections of the Chicago Area Transportation Study’s Intermodal Advisory Task Force, CATS Working Paper 97-17, 1997 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.