Routing For Taxi-pooling Problem Based on Ant Colony Optimization Algorithm

Xianmin Wei

Abstract


With the increasingly global environmental awareness, the city transportation strategy tends to be low-carbon and energy-saving. The most focuses of this trend is intelligent transportation. As a supplementary transportation tools between private transportation and public transportation, taxis have been the useful complement of the city public transportation system. The low-carbon and energy-saving way for taxis is called taxi-pooling. In this work, we focus on the routing problem of taxi-pooling. Specifically, with the analysis of the taxi-pooling problem, we investigate the characteristics and restraints, and construct an optimization model which aims to minimize the cost of passengers, maximize the benefit of drivers and maximize the load rate. To solve the above model, we propose to employ a modified Ant Colony Optimization (ACO) model. Our simulation results show that our method can effectively solve the taxi-pooling routing problem with the above three objectives.


Full Text:

PDF

References


Agatz N., Erera A., Savelsbergh M., Wang X. (2012). Optimization for dynamic ride-sharing: A review, European Journal of Operational Research, 223(2), 295–303. Doi: 10.1016/j.ejor.2012.05.028.

Agatz N.A.H., Erera A.L., Savelsbergh M.W.P., Wang X. (2011). Dynamic ride-sharing: A simulation study in metro Atlanta Original, Transportation Research Part B: Methodological, 45(9), 1450–1464. Doi: 10.1016/j.trb.2011.05.017.

Agatz N.A.H., Erera A.L., Savelsbergh M.W.P., Wang X. (2011). Dynamic ride-sharing: A simulation study in metro Atlanta, Transportation Research Part B: Methodological, 45(9), 1450–1464. Doi: 10.1016/j.trb.2011.05.017.

Athanasios Z., Dimitrios K. (2001). A Massively Parallel Time-Dependent Least-Time-Path Algorithm for Intelligent Transportation Systems Applications, Computer-Aided Civil and Infrastructure Engineering, 16(5), 337–346.

Barth M., Todd M. (1999). Simulation model performance analysis of a multiple station shared vehicle system, Transportation Research, 6, 238–243. Doi: 10.1016/S0968-090X(99)00021-2.

Branda˜o de Oliveira H.C., Vasconcelos, G.C. (2010). A hybrid search method for the vehicle routing problem with time windows, Annals of Operations Research, 180,125–144.

César R., Dorabela G., Fred G., Colin O. (2011). Traveling salesman problem heuristics: leading methods, implementations and latest advances, European Journal of Operational Research, 211(3), 427–441.

Chabini I.(1998). Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time, Transportation Research Records, 1645, 170–175. Doi: 10.3141/1645-21.

Chen J., Shen J., Ling Q., et al. (2003). Adaptive ant colony algorithm based on uniform distribution, Journal of software, 14(8), 1379–1387.

Chen L., Qin L., Chen H.J., et al. (2003). Ant colony algorithm with characteristics of sensation and consciousness, Journal of system simulation, 15(10), 1418–1425.

Cordeau J.F., Laporte G. (2006). A branch and – cut algorithm for the dial-a-ride problem, Operations Research, 3(26), 573–586.

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

Deneubourg J.L., et al. (1990). The self-organizing exploratory pattern of the argentine ant, Journal of insect behavior, 3(2), 159–168.

Diana M., Dessouky M.M. (2004). A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transportation Research Part B: Methodological, 38 (6), 539–557.

Diana M., Dessouky M.M. (2004). A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transportation Research Part B: Methodological, 38 (6), 539–557.

Dorer K., Calisti M. (2005). An Adaptive Solution to Dynamic Transport Optimization, in Proc 4th AAMAS (Autonomous Agents and Multi-agent Systems).

Dorigo M., Gambardella L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, 1(1), 53–66.

Duan H.B., Wang D.B., Yu X.F., et al. (2005). Study of improved ant colony algorithm based on cloud theory, Journal of Harbin Institute of Technology, 37(1), 115–119.

Huang G.D., Ling P., Wang Q. (2007). A hybrid metaheuristic ACO-GA with an application in sports competition scheduling, in Proc. - SNPD 2007: Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 611–616.

Huang G.R., Cao X.B., Wang X.F. (2004). Ant colony algorithm based on pheromone diffusion, Electronic Journal, 32 (5), 865–868.

Jaw J.J., Odoni A.R., Psaraftis H.N., Wilson N.H.M. (1986). A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows, Transportation Research Part B: Methodological, 20 (3), 243–257.

Jeffrey S.R., Gilad Z. (1994). Rules of Encounter-Designing Conventions for Automated Negotiation among Computers.

Kim S.S., Lee J.H. (1999). A study on design of dynamic route guidance system using forecasted travel time based on GPS data and modified shortest path algorithm, IEEE/IEEJ/JSAI International Conference on Intelligent Transportation Systems.

LAM T.N., TONG C.O. (1992). A dynamic route guidance system based on historical and current traffic pattern, in Proceedings of 1992 IEEE Intelligent Vehicle Symposium, 365–369.

Lee D.H., Wang H., Cheu R.L., Teo S.H. (2004). A taxi dispatch system based on current demands and real-time traffic information, Transportation Research Record., 1882, 193–200.

Li X., Luo X.H., Zhang J.H. (2004). Artificial ant colony optimization based on vector quantization codebook design calculation Method, Electronic Journal, 32(7), 1082–1085.

Liao Z.Q. (2001). Taxi dispatching via Global Positioning Systems, IEEE Transactions on Engineering Management, 3(48), 342–347.

Lu C., Wu Q. (2008). The study of taxi-pooling problem for urban residents, Road Traffic and Safety, 7 (5), 52–55.

Luo Y., Schonfeld P. (2007). A rejected-reinsertion heuristic for the static Dial-A-Ride Problem, Transportation Research Part B: Methodological, 41(7), 736–755.

Nagy G., Salhi S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, 162(1), 126–141.

Osman G., Aybars U. (2012). Improving performance of ACO algorithms using crossover mechanism based on mean of pheromone tables, in Proc. INISTA 2012 - International Symposium on INnovations in Intelligent SysTems and Applications.

Parragh S.N., Doerner K.F., Hartl R.F. (2010). Variable neighborhood search for the dial-a-ride problem, Computers & Operations Research, 37(6), 1129–1138.

Parragh S.N., Schmid V. (2013). Hybrid column generation and large neighborhood search for the dial-a-ride problem, Computers & Operations Research, 40(1), 490–497.

Pillac V., Gendreau M., Guéret C., Medaglia A. L. (2013). A review of dynamic vehicle routing problems, European Journal of Operational Research, 225 (1), 1–11.

Rilett L.R., Fu L. (1998). Expected shortest paths in dynamic and stochastic traffic networks,Elsevier Transportation Research Part B.

Schilde M., Doerner K.F., Hartl R.F. (2011). Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports, Computers & Operations Research, 38 (12), 1719–1730.

Sun X.M., Chu Y.X., Fan J.C., Yang Q.X. (2012). Research of Simulation on the Effect of Suspension Damping on Vehicle, Energy Procedia, 17, 145–151.

TaoC.C., Chen C.Y. (2007). Dynamix ride share matching algorithms for the taxipooling service based on intelligence transportation system technologies, International Conference on Management Science and Engineering, 400–402.

Tian Z.B., Tang L.X., Ren Y.M., Zhao Y.M., Wu C.X. (2009). Solving open-order slab matching problem by ACO with compound neighborhood, Zidonghua Xuebao/Acta Automatica Sinica, 186–192.

Wan C., Chen K. (2013). Study on connection of rail transit and bicycle traffic-a case study of Xi'an metro line, Applied Mechanics and Materials, 1933–1936.

WuY.H., Zhang N.Z. (2010). Vehicle routing problem improved particle swarm algorithm with time windows, Computer engineering and application, 46 (15), 230–234.

Yang Y., Song X.F., Wang J.F., et al. (2003). Ant colony algorithm for continuous space optimization problems, Decision and control, 18 (5), 573–576.

Zhang T., Chaovalitwongse W.A., Zhang Y.J. (2012). Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries, Computers & Operations Research, 39 (10), 2277–2290.

Zidi I., Mesghouni K., Zidi K., Ghedira K. (2012). A multi-objective simulated annealing for the multi-criteria dial a ride problem, Engineering Applications of Artificial Intelligence, 25(6), 1121–1131.


Refbacks

  • There are currently no refbacks.


Revista de la Facultad de Ingeniería,

ISSN: 2443-4477; ISSN-L:0798-4065

Edif. del Decanato de la Facultad de Ingeniería,

3º piso, Ciudad Universitaria,

Apartado 50.361, Caracas 1050-A,

Venezuela.

© Universidad Central de Venezuela