A revised branch-and-price algorithm for dial-a-ride problems with the consideration of time-dependent travel cost

Ta Yin Hu, Chin Ping Chang

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

Summary Developing demand responsive transit systems are important with regard to meeting the travel needs for elderly people. Although Dial-a-ride Problems (DARP) have been discussed for several decades, most researchers have worked to develop algorithms with low computational cost under the minimal total travel costs, and fewer studies have considered how changes in travel time might affect the vehicle routes and service sequences. Ignoring such variations in travel time when design vehicle routes and schedules might lead to the production of inefficient vehicle routes, as well as incorrect actual vehicle arrival times at the related nodes. The purpose of this paper is to construct a DARP formulation with consideration of time-dependent travel times and utilizes the traffic simulation software, DynaTAIWAN, to simulate the real traffic conditions in order to obtain the time-dependent travel time matrices. The branch-and-price approach is introduced for the time-dependent DARP and tested by examining the sub-network of Kaohsiung City, Taiwan. The numerical results reveal that the length of the time window can significantly affect the vehicle routes and quantitative measurements. As the length of the time window increases, the objective value and the number of vehicles will reduce significantly. However, the CPU time, the average pickup delay time, the average delivery delay time and the average actual ride time (ART)/direct ride time (DRT) will increase significantly as the length of the time window increases. Designing the vehicle routes to reduce operating costs and satisfy the requirements of customers is a difficult task, and a trade-off must be made between these goals.

Original languageEnglish
Pages (from-to)700-723
Number of pages24
JournalJournal of Advanced Transportation
Volume49
Issue number6
DOIs
Publication statusPublished - 2015 Oct 1

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Economics and Econometrics
  • Mechanical Engineering
  • Computer Science Applications
  • Strategy and Management

Fingerprint Dive into the research topics of 'A revised branch-and-price algorithm for dial-a-ride problems with the consideration of time-dependent travel cost'. Together they form a unique fingerprint.

Cite this