Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-23T20:59:15.935Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal network design for an on-demand transport system

Published online by Cambridge University Press:  31 March 2006

ZHIJIE CAI  and
XINYAN LI
ZHIJIE CAI
Affiliation:
School of Mathematical Sciences, Fudan University, Shanghai 200433, China email: [email protected]
XINYAN LI
Affiliation:
School of Mathematical Sciences, Fudan University, Shanghai 200433, China email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The design of an on-demand transport system with origin and destination matrices is studied. Two objectives are considered; one is to minimize the sum (over all users) of travel time per unit time and the other is to minimize the sum of the total cost of track built. Firstly, we show that even the minimum total cost problem without consideration of the travel time is not a simple minimum spanning tree problem. Then, for the bi-objective problem, we transform one objective to a constraint condition. With this transformation, we transform the bi-objective problem to a single-objective problem and give the optimal solution by the branch and bound method. Finally, we propose a fast approximate algorithm and analyze its complexity.

Type
Papers
Information
European Journal of Applied Mathematics , Volume 17 , Issue 2 , April 2006 , pp. 129 - 140
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

The project is supported by the National Natural Science Foundation of China (No.10201008) and Royal Society Grant to Promote Study Groups with Industry in China. The problem was presented by Martin Lowson (Advanced Transport Systems Ltd.) at the 46th European Study Group with Industry.