Differential evolution for urban transit routing problem
The urban transit routing problem (UTRP) involves the construction of route sets on existing road networks to cater for the transit demand efficiently. This is an NP-hard problem, where the generation of candidate route sets can lead to a number of potential routes being discarded on the grounds of...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Scientific Research Publishing
2016
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/55522/ http://psasir.upm.edu.my/id/eprint/55522/1/Differential%20Evolution%20for%20Urban%20Transit%20Routing.pdf |
| _version_ | 1848852825516277760 |
|---|---|
| author | Buba, Ahmed Tarajo Lai, Soon Lee |
| author_facet | Buba, Ahmed Tarajo Lai, Soon Lee |
| author_sort | Buba, Ahmed Tarajo |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | The urban transit routing problem (UTRP) involves the construction of route sets on existing road networks to cater for the transit demand efficiently. This is an NP-hard problem, where the generation of candidate route sets can lead to a number of potential routes being discarded on the grounds of infeasibility. This paper presents a new repair mechanism to complement the existing terminal repair and the make-small-change operators in dealing with the infeasibility of the candidate route set. When solving the UTRP, the general aim is to determine a set of transit route networks that achieves a minimum total cost for both the passenger and the operator. With this in mind, we propose a differential evolution (DE) algorithm for solving the UTRP with a specific objective of minimizing the average travel time of all served passengers. Computational experiments are performed on the basis of benchmark Mandl’s Swiss network. Computational results from the proposed repair mechanism are comparable with the existing repair mechanisms. Furthermore, the combined repair mechanisms of all three operators produced very promising results. In addition, the proposed DE algorithm outperformed most of the published results in the literature. |
| first_indexed | 2025-11-15T10:44:14Z |
| format | Article |
| id | upm-55522 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T10:44:14Z |
| publishDate | 2016 |
| publisher | Scientific Research Publishing |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-555222017-09-13T03:31:21Z http://psasir.upm.edu.my/id/eprint/55522/ Differential evolution for urban transit routing problem Buba, Ahmed Tarajo Lai, Soon Lee The urban transit routing problem (UTRP) involves the construction of route sets on existing road networks to cater for the transit demand efficiently. This is an NP-hard problem, where the generation of candidate route sets can lead to a number of potential routes being discarded on the grounds of infeasibility. This paper presents a new repair mechanism to complement the existing terminal repair and the make-small-change operators in dealing with the infeasibility of the candidate route set. When solving the UTRP, the general aim is to determine a set of transit route networks that achieves a minimum total cost for both the passenger and the operator. With this in mind, we propose a differential evolution (DE) algorithm for solving the UTRP with a specific objective of minimizing the average travel time of all served passengers. Computational experiments are performed on the basis of benchmark Mandl’s Swiss network. Computational results from the proposed repair mechanism are comparable with the existing repair mechanisms. Furthermore, the combined repair mechanisms of all three operators produced very promising results. In addition, the proposed DE algorithm outperformed most of the published results in the literature. Scientific Research Publishing 2016-11 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/55522/1/Differential%20Evolution%20for%20Urban%20Transit%20Routing.pdf Buba, Ahmed Tarajo and Lai, Soon Lee (2016) Differential evolution for urban transit routing problem. Journal of Computer and Communications, 4. pp. 11-25. ISSN 2327-5219; ESSN: 2327-5227 http://file.scirp.org/pdf/JCC_2016111114103587.pdf 10.4236/jcc.2016.414002 |
| spellingShingle | Buba, Ahmed Tarajo Lai, Soon Lee Differential evolution for urban transit routing problem |
| title | Differential evolution for urban transit routing problem |
| title_full | Differential evolution for urban transit routing problem |
| title_fullStr | Differential evolution for urban transit routing problem |
| title_full_unstemmed | Differential evolution for urban transit routing problem |
| title_short | Differential evolution for urban transit routing problem |
| title_sort | differential evolution for urban transit routing problem |
| url | http://psasir.upm.edu.my/id/eprint/55522/ http://psasir.upm.edu.my/id/eprint/55522/ http://psasir.upm.edu.my/id/eprint/55522/ http://psasir.upm.edu.my/id/eprint/55522/1/Differential%20Evolution%20for%20Urban%20Transit%20Routing.pdf |