Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times
This paper addresses a variant of bus timetabling problem assuming that travel times changes dynamically over the planning horizon. In addition to minimizing the transfer waiting time, another objective, namely minimizing the fruitless waiting time, is introduced in this paper as a new realistic obj...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Amirkabir University of Technology
2020-02-01
|
| Series: | AUT Journal of Mathematics and Computing |
| Subjects: | |
| Online Access: | https://ajmc.aut.ac.ir/article_3323_85cc256ebddca4a51b227d38698683da.pdf |
| _version_ | 1797307156428488704 |
|---|---|
| author | Javad Zamani Kafshani Seyyed Ali Mirhassani Farnaz Hooshmand |
| author_facet | Javad Zamani Kafshani Seyyed Ali Mirhassani Farnaz Hooshmand |
| author_sort | Javad Zamani Kafshani |
| collection | DOAJ |
| description | This paper addresses a variant of bus timetabling problem assuming that travel times changes dynamically over the planning horizon. In addition to minimizing the transfer waiting time, another objective, namely minimizing the fruitless waiting time, is introduced in this paper as a new realistic objective. First, the problem is formulated as a mixed integer linear programming model. Then, since commercial solvers become inefficient to solve moderate and large sized instances of the problem (due to the NP-hardness), a GRASP heuristic algorithm is developed. Computational experiments over a variety of random instances verify the performance of the proposed method. |
| first_indexed | 2024-03-08T00:52:09Z |
| format | Article |
| id | doaj.art-a6d4bccc35e647dcb156c9291e3c706c |
| institution | Directory Open Access Journal |
| issn | 2783-2449 2783-2287 |
| language | English |
| last_indexed | 2024-03-08T00:52:09Z |
| publishDate | 2020-02-01 |
| publisher | Amirkabir University of Technology |
| record_format | Article |
| series | AUT Journal of Mathematics and Computing |
| spelling | doaj.art-a6d4bccc35e647dcb156c9291e3c706c2024-02-14T19:33:07ZengAmirkabir University of TechnologyAUT Journal of Mathematics and Computing2783-24492783-22872020-02-011112513410.22060/ajmc.2019.15497.10183323Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting timesJavad Zamani Kafshani0Seyyed Ali Mirhassani1Farnaz Hooshmand2Amirkabir University of TechnologyDepartment of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic)Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic)This paper addresses a variant of bus timetabling problem assuming that travel times changes dynamically over the planning horizon. In addition to minimizing the transfer waiting time, another objective, namely minimizing the fruitless waiting time, is introduced in this paper as a new realistic objective. First, the problem is formulated as a mixed integer linear programming model. Then, since commercial solvers become inefficient to solve moderate and large sized instances of the problem (due to the NP-hardness), a GRASP heuristic algorithm is developed. Computational experiments over a variety of random instances verify the performance of the proposed method.https://ajmc.aut.ac.ir/article_3323_85cc256ebddca4a51b227d38698683da.pdfbus timetablingdynamic travel timetransfer waiting timefruitless waiting timegrasp |
| spellingShingle | Javad Zamani Kafshani Seyyed Ali Mirhassani Farnaz Hooshmand Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times AUT Journal of Mathematics and Computing bus timetabling dynamic travel time transfer waiting time fruitless waiting time grasp |
| title | Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times |
| title_full | Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times |
| title_fullStr | Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times |
| title_full_unstemmed | Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times |
| title_short | Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times |
| title_sort | adopting grasp to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times |
| topic | bus timetabling dynamic travel time transfer waiting time fruitless waiting time grasp |
| url | https://ajmc.aut.ac.ir/article_3323_85cc256ebddca4a51b227d38698683da.pdf |
| work_keys_str_mv | AT javadzamanikafshani adoptinggrasptosolveanovelmodelforbustimetablingproblemwithminimumtransferandfruitlesswaitingtimes AT seyyedalimirhassani adoptinggrasptosolveanovelmodelforbustimetablingproblemwithminimumtransferandfruitlesswaitingtimes AT farnazhooshmand adoptinggrasptosolveanovelmodelforbustimetablingproblemwithminimumtransferandfruitlesswaitingtimes |