[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The integrated dial-a-ride problem with timetabled fixed route service

  • Original Paper
  • Published:
Public Transport Aims and scope Submit manuscript

Abstract

This paper concerns operational planning of door-to-door transportation systems for the elderly and/or disabled, who often need a more flexible transportation system than the rest of the population. Highly flexible, but very costly direct transportation is often offered as a complement to standard fixed route public transport service. In the integrated dial-a-ride problem (IDARP), these modes of transport are combined and certain legs of the passengers journeys may be performed with the fixed route public transport system. We extend the IDARP and include timetables for the fixed route services, forcing the fleet of vehicles to schedule the arrival at transfer locations with care. Two mixed integer linear programming formulations of the integrated dial-a-ride problem with timetables are presented and analyzed. The key modeling challenge is that of the transfers between the fleet of vehicles and the fixed route public transport system. The formulations differ in how the transfers are modeled and the differences are thoroughly discussed. The computational study compares the formulations in terms of network size, computational time and memory usage and conclusions about their performances are drawn.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The computations were performed using CPLEX 12.5 on a virtual machine with four CPU’s (Intel E5-2650) that have two cores each and 24 GB internal memory.

References

  • Aldaihani M, Dessouky MM (2003) Hybrid scheduling methods for paratransit operations. Comput Ind Eng 45(1):75–96

    Article  Google Scholar 

  • Chowdhury S, Ceder A (2016) Users willingness to ride an integrated public-transport service: a literature review. Transp Policy 48:183–195

    Article  Google Scholar 

  • Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper Res 54(3):573–586

    Article  Google Scholar 

  • Cordeau JF, Laporte G (2007) The dial-a-ride problem: models and algorithms. Ann Oper Res 153(1):29–46

    Article  Google Scholar 

  • Cortés CE, Matamala M, Contardo C (2010) The pickup and delivery problem with transfers: formulation and a branch-and-cut solution method. Eur J Oper Res 200(3):711–724

    Article  Google Scholar 

  • Crainic T, Malucelli F, Nonato M (2001) Flexible many-to-few + few-to-many = an almost personalized transit system. In: Proceedings of the triennial symposium on transportation analysis: TRISTAN IV, pp 435–440

  • Deleplanque S, Quilliot A (2013) Transfers in the on-demand transportation: the DARPT Dial-a-Ride Problem with transfers allowed. In: Multidisciplinary international scheduling conference: theory and applications (MISTA), pp 185–205

  • Edwards D, Elangovan A, Watkins K (2012) Reaching low-density urban areas with the network-inspired transportation system. In: 15th international IEEE conference on intelligent transportation systems (ITSC), pp 826–831

  • Edwards D, Trivedi A, Elangovan A, Dickerson S (2011) The network-inspired transportation system: A hierarchical approach to integrated transit. In: 14th IEEE conference on intelligent transportation systems (ITSC), pp 1507–1512

  • Ghilas V, Demir E, Woensel TV (2016) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines. Comput Oper Res 72:12–30

    Article  Google Scholar 

  • Häll CH, Lundgren JT, Värbrand P (2008) Evaluation of an integrated public transport system: a simulation approach. Arch Transp 20(1–2):29–46

    Google Scholar 

  • Häll CH, Andersson H, Lundgren JT, Värbrand P (2009) The integrated dial-a-ride problem. Public Transp 1(1):39–54

    Article  Google Scholar 

  • Hickman M, Blume K (2001) Modeling cost and passenger level of service for integrated transit service. In: Voß S, Daduna JR (eds) Computer-aided scheduling of public transport, vol 505., Lecture Notes in Economics and Mathematical SystemsSpringer, Berlin, pp 233–251

    Chapter  Google Scholar 

  • Horn ME (2002) Multi-modal and demand-responsive passenger transport systems: a modelling framework with embedded control systems. Transp Res Part A Policy Pract 36(2):167–188

    Article  Google Scholar 

  • Horn MET (2004) Procedures for planning multi-leg journeys with fixed-route and demand-responsive passenger transport services. Transp Res Part C Emerg Technol 12(1):33–55

    Article  Google Scholar 

  • Knutsson S (2003) Valuing rider quality in Swedish special transport services—new findings. J Public Transp 6(3):4

    Article  Google Scholar 

  • Liaw CF, White C III, Bander J (1996) A decision support system for the bimodal dial-a-ride problem. IEEE Trans Syst Man Cybern Part A Syst Hum 26(5):552–565

    Article  Google Scholar 

  • Li H, Lim A (2003) A metaheuristic for the pickup and delivery problem with time windows. Int J Artif Intell Tools 12(02):173–186

    Article  Google Scholar 

  • Masson R, Lehuédé F, Péton O (2014) The dial-a-ride problem with transfers. Comput Oper Res 41:12–23

    Article  Google Scholar 

  • Paquette J, Cordeau JF, Laporte G (2009) Quality of service in dial-a-ride operations. Comput Ind Eng 56(4):1721–1734

    Article  Google Scholar 

  • Potter B (1976) Ann Arbor’s dispatching system. Transportation Research Record (608)

  • Rais A, Alvelos F, Carvalho MS (2014) New mixed integer-programming model for the pickup-and-delivery problem with transshipment. Eur J Oper Res 235(3):530–539

    Article  Google Scholar 

  • Ronald N, Thompson R, Winter S (2015) Simulating demand-responsive transportation: a review of agent-based approaches. Transp Rev 35(4):404–421

    Article  Google Scholar 

  • Stålhane M, Andersson H, Christiansen M, Fagerholt K (2014) Vendor managed inventory in tramp shipping. Omega 47:60–72

    Article  Google Scholar 

  • The Swedish Bus and Coach Federation (2015) Statistik om bussbranschen 2015. Tech. rep, Stockholm

    Google Scholar 

  • Toth P, Vigo D (2014) Vehicle routing: problems, methods, and applications, vol 18. SIAM, Philadelphia

    Book  Google Scholar 

  • Uchimura K, Takahashi H, Saitoh T (2002) Demand responsive services in hierarchical public transportation system. IEEE Trans Veh Technol 51(4):760–766

    Article  Google Scholar 

  • Wilson N, Weissberg R, Hauser J (1976) Advanced dial-a-ride algorithms research project: final report. Research report, Massachusetts Institute of Technology, Department of Materials Science and Engineering

Download references

Acknowledgements

This research is part of a project financed by the Swedish Governmental Agency for Innovation Systems (VINNOVA). The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Science and Technology (ITN), Linköping University, 60174, Norrköping, Sweden

    Marcus Posada & Carl H. Häll

  2. Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491, Trondheim, Norway

    Henrik Andersson

Authors
  1. Marcus Posada
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Henrik Andersson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Carl H. Häll
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marcus Posada.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Posada, M., Andersson, H. & Häll, C.H. The integrated dial-a-ride problem with timetabled fixed route service. Public Transp 9, 217–241 (2017). https://doi.org/10.1007/s12469-016-0128-9

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12469-016-0128-9

Keywords

Search

Navigation