An exact algorithm for vehicle routing and scheduling problem of free pickup and delivery service in flight ticket sales companies based on set-partitioning model

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

29 Scopus Citations
View graph of relations

Author(s)

  • Gang Dong
  • Jiafu Tang
  • Kin Keung Lai
  • Yuan Kong

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)789-799
Journal / PublicationJournal of Intelligent Manufacturing
Volume22
Issue number5
Publication statusPublished - Oct 2011

Abstract

This paper addresses a vehicle routing and scheduling problem arising in Flight Ticket Sales Companies for the service of free pickup and delivery of airline passengers to the airport. The problem is formulated under the framework of Vehicle Routing Problem with Time Windows (VRPTW), with the objective of minimizing the total operational costs, i.e. fixed start-up costs and variable traveling costs. A 0-1 mixed integer programming model is presented, in which service quality is factored in constraints by introducing passenger satisfaction degree functions that limit time deviations between actual and desired delivery times. The problem addressed in this paper has two distinctive characteristics-small vehicle capacities and tight delivery time windows. An exact algorithm based on the set-partitioning model, concerning both characteristics, is developed. In the first phase of the algorithm the entire candidate set of best feasible routes is generated, and then the optimal solution is obtained by solving the set-partitioning model in the second phase. Finally, we use four actual instances to illustrate application of the proposed algorithm. Moreover, the proposed algorithm is applied to a random instance containing more orders to verify the general effectiveness of the proposed algorithm even if the number of passengers increases in future. © 2009 Springer Science+Business Media, LLC.

Research Area(s)

  • Exact Algorithm, Flight ticket sales company, Free pickup and delivery service, Routing and scheduling, Set-partitioning model

Citation Format(s)

An exact algorithm for vehicle routing and scheduling problem of free pickup and delivery service in flight ticket sales companies based on set-partitioning model. / Dong, Gang; Tang, Jiafu; Lai, Kin Keung; Kong, Yuan.

In: Journal of Intelligent Manufacturing, Vol. 22, No. 5, 10.2011, p. 789-799.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review