Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm
This paper addresses a biobjective bus routing problem that pays attention to both the routing cost and the total distance walked by the individuals to reach their assigned pickup point. These two objectives are conflicting. Generally, the less the individuals walk, the more the number of visited pi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-04-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/9/1390 |
| _version_ | 1797503896738856960 |
|---|---|
| author | Herminia I. Calvete Carmen Galé José A. Iranzo |
| author_facet | Herminia I. Calvete Carmen Galé José A. Iranzo |
| author_sort | Herminia I. Calvete |
| collection | DOAJ |
| description | This paper addresses a biobjective bus routing problem that pays attention to both the routing cost and the total distance walked by the individuals to reach their assigned pickup point. These two objectives are conflicting. Generally, the less the individuals walk, the more the number of visited pickup points and so the more the routing cost. In addition, the problem deals with finding the set of pickup points visited among the set of potential locations, identifying the set of individuals assigned to each visited pickup point, and designing the bus routes. Taking into account the highly combinatorial nature of the problem, an evolutionary algorithm is proposed to approach the associated Pareto front. Its main novelties are twofold. The first is the way in which the chromosomes are encoded since they only provide information about the number of routes and the visited pickup points. The second novelty lies in the procedure to construct a feasible solution from the chromosome, which involves a heuristic and several local search procedures to improve both objective functions. Computational experiments are carried out to check the performance of the algorithm in terms of the quality of the Pareto front yielded. |
| first_indexed | 2024-03-10T03:56:55Z |
| format | Article |
| id | doaj.art-c3fa760e5387404ead48a46a6d01e745 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T03:56:55Z |
| publishDate | 2022-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-c3fa760e5387404ead48a46a6d01e7452023-11-23T08:43:35ZengMDPI AGMathematics2227-73902022-04-01109139010.3390/math10091390Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary AlgorithmHerminia I. Calvete0Carmen Galé1José A. Iranzo2Statistical Methods Department, IUMA, University of Zaragoza, Pedro Cerbuna 12, 50009 Zaragoza, SpainStatistical Methods Department, IUMA, University of Zaragoza, María de Luna 3, 50018 Zaragoza, SpainStatistical Methods Department, IUMA, University of Zaragoza, Violante de Hungría 23, 50009 Zaragoza, SpainThis paper addresses a biobjective bus routing problem that pays attention to both the routing cost and the total distance walked by the individuals to reach their assigned pickup point. These two objectives are conflicting. Generally, the less the individuals walk, the more the number of visited pickup points and so the more the routing cost. In addition, the problem deals with finding the set of pickup points visited among the set of potential locations, identifying the set of individuals assigned to each visited pickup point, and designing the bus routes. Taking into account the highly combinatorial nature of the problem, an evolutionary algorithm is proposed to approach the associated Pareto front. Its main novelties are twofold. The first is the way in which the chromosomes are encoded since they only provide information about the number of routes and the visited pickup points. The second novelty lies in the procedure to construct a feasible solution from the chromosome, which involves a heuristic and several local search procedures to improve both objective functions. Computational experiments are carried out to check the performance of the algorithm in terms of the quality of the Pareto front yielded.https://www.mdpi.com/2227-7390/10/9/1390bus routing problembiobjectiveevolutionarylocal searchschoolworkplace |
| spellingShingle | Herminia I. Calvete Carmen Galé José A. Iranzo Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm Mathematics bus routing problem biobjective evolutionary local search school workplace |
| title | Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm |
| title_full | Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm |
| title_fullStr | Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm |
| title_full_unstemmed | Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm |
| title_short | Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm |
| title_sort | approaching the pareto front in a biobjective bus route design problem dealing with routing cost and individuals walking distance by using a novel evolutionary algorithm |
| topic | bus routing problem biobjective evolutionary local search school workplace |
| url | https://www.mdpi.com/2227-7390/10/9/1390 |
| work_keys_str_mv | AT herminiaicalvete approachingtheparetofrontinabiobjectivebusroutedesignproblemdealingwithroutingcostandindividualswalkingdistancebyusinganovelevolutionaryalgorithm AT carmengale approachingtheparetofrontinabiobjectivebusroutedesignproblemdealingwithroutingcostandindividualswalkingdistancebyusinganovelevolutionaryalgorithm AT joseairanzo approachingtheparetofrontinabiobjectivebusroutedesignproblemdealingwithroutingcostandindividualswalkingdistancebyusinganovelevolutionaryalgorithm |