An Adapted Non-dominated Sorting Algorithm (ANSA) for Solving Multi Objective Trip Distribution Problem


School of Engineering, Damghan University, Damghan, Iran.


Trip distribution deals with estimation of trips distributed among origins and destinations and is one of the important stages in transportation planning. Since in the real world, trip distribution models often have more than one objective, multi-objective models are developed to cope with a set of conflict goals in this area. In a proposed method of adapted non-dominated sorting algorithm (ANSA) is introduced and applied on a multi objective trip distribution model. The objectives considered are: (1) maximization of the interactivity of the system, (2) minimization of the generalized costs and (3) minimization of the deviation from the observed year. in proposed ANSA using the sorting process of NSGA II and two proposed adapted operators a new adapted algorithm is introduced and applied to solve the three-objective model. To test the performance of the proposed algorithm, a set of Hong Kong data is used and results of applying proposed algorithm is compared to other models of the literature. The results show that proposed algorithms has better performance rather than the algorithms of the literature.


1. V.T. Arasan, M. Wermuth, and B.S. Srinivas, Modeling of stratified urban tripdistribution, J. TranspEng, 122 (1996) 342-346.

2. M.M.M. Abdel-Aal, Calibrating a trip distribution gravity model stratified by the trip purposes for the city of Alexandria, Alexandria Engineering Journal, 53 (2014) 677-689.

3. M.J. Bruton, Introduction to Transportation Planning, UCL Press, London (1985).

4. B. Cakir, F. Altiparmak, and B. Dengiz, Multi-objective optimization of astochastic assembly line balancing: A hybrid simulated annealing algorithm, Computer & Industrial Engineering, 60 (2011) 376-384.

5. P. Czyzak, A. Jaszkiewicz, Pareto simulated annealing: A metaheuristic technique for multipleobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7 (1998) 34-47 .

6. L.N. Duffus, A.S. Alfa, and A.H. Soliman, The reliability of using the gravity model for forecasting trip distribution, Transportation, 14 (1987) 175-192.

7. M.M. El-Sherbiny, R.M. Alhamali, A hybrid particle swarm algorithm with artificial immune learning for solving the fixed charge transportation problem, Computers & Industrial Engineering, 64 (2013) 610-620.

8. A. Hallefjord, K. Jornsten, Gravity models with multiple objectives: theory and applications, Trans Res B., 20 (1986) 19-39.

9. S. Islam, S., Kumar Roy, A new fuzzy multi-objective programming: Entropy based geometric programming and its application of transportation problems, European Journal of Operational Research, 173 (2006) 387-404.

10. S. Kirkpatrick, C.D. Gellat, and M.P. Vecchi, Optimization by simulated annealing. Science, 220 (1983) 671-680.

11. M. Kompil, H.M. Celik, Modelling trip distribution with fuzzy and genetic fuzzy systems, Transportation Planning and Technology, 36(2) (2013) 170-200.

12. X. Li, Z. Qin, L. Yang, and K. Li, Entropy maximization model for the trip distribution problem with fuzzy and random parameters, Journal of Computational and Applied Mathematics, 235 (2011) 1906-1913.

13. K.S. Lin, D.A. Niemeier, Temporal disaggregation of travel demand for high resolution emissions inventories, Trans Res 3D, (1998) 375-387.

14. C. Murat, Sample size needed for calibrating trip distribution and behavior of the gravity model, Journal of Transport Geography, 18 (1994) 183-190.

15. S. Ortuzar, L.G. Willumsen, Modeling Transport, Wiley, New York (1994).

16. M.S. Sabbagh, H. Ghafari, and S.R. Mousavi, A new hybrid algorithm for the balanced transportation problem, Computers & Industrial Engineering, 82 (2015) 115-126.

17. Salminen. S. Trafic accidents during work and work commuting, Int J IndErgon 26,75-85 (2000)

18. T. Thomas, S.I.A. Tutert, An empirical model for trip distribution of commuters in The Netherlands: transferability in time and space reconsidered, Journal of Transport Geography, 26 (2013) 158-165.

19. A.G. Wilson, Entropy in urban and regional modeling, Poin, England (1970).

20. A. Zaretalab, V. Hajipour, M. Sharifi, and M.R. Shahriari, A knowledge-based archive multi-objective simulated annealingalgorithm to optimize series parallel system with choice of redundancy strategies. Computers & Industrial Engineering, 80 (2015) 33-44.

21. Z. Zhou, A. Chen, S.C. Wong, Alternative formulations of a combined trip generation, trip distribution, modal split and trip assignment model, European Journal of Operational Research, 198 (2009) 129-138.