A Branch-and-price Algorithm for Dial-a-ride Problems under Time-dependent Travel Costs with Consideration of Service Quality

  • 張 清濱

Student thesis: Doctoral Thesis

Abstract

According to census from the Ministry of The Interior in Taiwan the number of people aged 65 and over as a proportion of the global population is 9 9% in 2006 and the government forecasts that the number of people aged 65 and over as a proportion of the global population will expand to 11 6% in 2014 National Development Council Taiwan indicated that the number of people aged 65 and over as a proportion of the global population will increase to 41 00% in 2061 To meet the transportation demands for the elderly and handicapped people proving the dial-a-ride systems to ensure the quality of transportation service is an important issue for governments Well-designed vehicle routes and schedule for dial-a-ride systems can improve transportation efficiency and save total travel costs How to design an appropriate vehicle routes and schedule is a critical work for dial-a-ride problems (DARP) For the study of the DARP most literatures consider the minimum travel costs to construct solution framework or formulate mathematical model and then apply appropriate algorithms or heuristic procedures to solve based on the scale and complexity of the problem However in practice the DARP not only takes into account the operational costs but also the customer satisfaction Seldom studies explore the quality of service for customers in DARP The purpose of this paper is to consider customer satisfaction to formulate the mathematical model In this research the quality of service for customers are quantitated as measurable indexes including the average pickup delay time average delivery delay time and the ratio of actual ride time to direct ride time (ART/DRT) The branch-and-price approach is applied to solve DARP with time-dependent travel costs and consideration for the service quality of customers The ε-constraint method is introduced to consider two contradictory objectives: minimum total travel time and minimum the average pickup delay time simultaneously to obtain non-dominated solutions The traffic simulation software DynaTAIWAN (Hu et al 2007) is uesd to generate time-dependent travel time matrices and simulate traffic flows in the real network Numerical experiments are conducted in a Kaohsiung network 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 ART/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 work and a trade-off must be made between these goals
Date of Award2015 Feb 6
Original languageEnglish
SupervisorTa-Yin Hu (Supervisor)

Cite this

A Branch-and-price Algorithm for Dial-a-ride Problems under Time-dependent Travel Costs with Consideration of Service Quality
清濱, 張. (Author). 2015 Feb 6

Student thesis: Doctoral Thesis