Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Optimization of a Semiflexible Demand-Responsive Feeder System in Suburban Areas Using a Memetic Algorithm

Optimization of a Semiflexible Demand-Responsive Feeder System in Suburban Areas Using a Memetic... Hindawi Journal of Advanced Transportation Volume 2023, Article ID 7593649, 18 pages https://doi.org/10.1155/2023/7593649 Research Article Optimization of a Semiflexible Demand-Responsive Feeder System in Suburban Areas Using a Memetic Algorithm 1 2 1 Fabio Sartori Vieira , Kenneth Sorensen , and Pieter Vansteenwegen KU Leuven, KU Leuven Institute for Mobility CIB, Leuven, Belgium ANT/OR University of Antwerp Operations Research Group, Antwerp, Belgium Correspondence should be addressed to Fabio Sartori Vieira; fabio.vieira@kuleuven.be Received 6 September 2022; Revised 6 January 2023; Accepted 18 January 2023; Published 15 February 2023 Academic Editor: Zhihong Yao Copyright © 2023 Fabio Sartori Vieira et al. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Traditional bus operations in suburban areas are inefcient due to their fxed routes and timetables. Since suburban operations deal with low demand spread in a large area, the service stays underused for most of-peak hours. In order to render the operation proftable and increase the number of passengers on each bus, operators reduce the frequency of the service, which results in an increase of passenger waiting time for the service. As a solution to this problem, this paper introduces a demand- responsive public bus system that aims to adjust routes and timetables of a semifexible system to the demand for trans- portation. Te operation still ofers a reliable service like the traditional system but aims to reduce the passenger travel time. A memetic algorithm is developed to optimize this demand-responsive system. For a network with 25 bus stops served hourly by three lines and with an average demand of 20 requests per hour, the memetic algorithm is demonstrated to reduce the passenger waiting time with almost 50% in comparison with a traditional system operating in the same network with fxed routes and timetable. hours, feeder lines with fxed routes and timetables are no 1. Introduction longer efcient. Teir service is typically optimized for the Te growth of (sub)urban areas around big cities, such as demand predicted based on historical data, without con- new neighborhoods or settlements that operate as com- sidering external factors that might infuence the daily de- muting towns, puts pressure on public transportation mand using the service, such as weather conditions or systems. Tese new urban areas generally have a low nonregular events. population density spread over a large area. Direct con- Another approach to address this type of demand are nections or extensions of the current routes of the public fully fexible demand-responsive (taxi) services, which transport system potentially lead to a nonproftable service. operate without using fxed routes or timetables but pick up In order to improve the public transportation system in and drop of passengers according to their needs in a service complimentary to the traditional transit system, typically in these areas, the most applied solution is the implementa- tion of feeder lines. Feeder lines zigzag through the sub- a door-to-door service. In the OR literature, such systems are urban area to bring passengers to a hub station where a often modeled as a variant of the Dial-a-Ride Problem high-frequency service ofers a direct and fast connection to (DARP). Despite being a very responsive service, the op- the demand centers (city center, industrial zones, and eration of such systems in suburban areas with low demand schools). can also lead to low seat occupancy, and consequently, an Feeder lines partially solve the efciency problem in expensive operation. suburban areas with low demand, especially during peak Tis paper aims to investigate the applicability of a hours. However, when demand is lower during of-peak semifexible demand-responsive transportation system 2 Journal of Advanced Transportation experiments are performed for these instances. One last replacing a traditional feeder system in suburban areas. Te fact that this system is semifexible is a key novelty. experiment considers a large network and instances with more requests. Section 6 concludes the paper and dis- Tis means, on the one hand, it has some characteristics of traditional systems, i.e., a regular frequency of operation, cusses opportunities for further research. predefned standard routes, and a stop-based service. Tis “backbone” makes this system recognizable for the users 2. Literature Review and lowers the threshold for using it. Tus, this system still serves the demand by relying on the structure of the Tis section frst discusses the uprise of demand-responsive traditional feeder system. On the other hand, it is a de- systems, with diferent levels of fexibility. Ten, the DRFS is mand-responsive system, allowing modifcations to the positioned in the state of the art and various closely related standard routes and adjusting the timetable of each trip systems are discussed. while respecting the initial frequency. Terefore, our As an alternative for traditional systems, demand- proposed system falls in the category of a semifexible responsive systems emerged in the last decades and their demand-responsive feeder systems (DRFS) and intends to popularity has been rising over the years. One of the ofer an optimized service with some level of respon- initial, yet still popular, demand-responsive systems is a siveness to the actual demand for transportation yet still door-to-door dial-a-ride (DAR) system with the purpose based on a service running regularly. It should also be of transporting reduced-mobility or elderly passengers, noted that the same resources are being used as in the typically running in parallel to a fxed service [1]. Such a traditional system, so the operator costs remain the same system is also used as a transportation mode for rural and the focus will be on ofering a better service, with communities without scheduled bus services. Tis fully roughly the same operational costs. fexible system is typically operated based on reservations. As the traditional system, our semifexible DRFS is stop- After the surge of more innovative solutions and intel- based. It means that passengers willing to submit a request ligent transportation systems (ITS), more demand-re- must indicate beforehand their origin bus stop and walk to sponsive transport systems were developed for a wider the stop at the preferred departure time. Requests for a trip variety of purposes, complementing the fxed trans- can be submitted until just before the operation starts. Based portation systems [2–5]. on a list with all passenger requests, the routes and departure Several papers explore case studies to improve the times for the buses operating each line are optimized for current transit operation systems in rural areas (i.e., see [6]), each hour of operation of the services. Te objective when the implementation of alternative DRT systems and other optimizing the operations of this DRFS is to minimize the modes of operation (i.e., see [7]), or the optimal redesign of sum of the travel times for all passengers, from the moment the DRT systems to increase efciency [8]. Te common they arrive at the bus stop until they arrive at the hub station. characteristic identifed in transit operation in suburban or Terefore, a memetic algorithm (MA) is introduced to rural areas is the necessity of subsidies to make the service optimize the performance of the DRFS from the users’ viable. Terefore, it should be noted that our semifexible perspective. DRFS uses roughly the same resources as the traditional Te main contributions of this paper are that we in- feeder systems. troduce and analyze a new, semifexible, demand-responsive Depending on the transportation system proposed, feeder system, designed for low demand suburban areas. diferent levels of fexibility are considered that may afect Diferent from the other DRT systems, our semifexible stops, routes, timetables, or prebooking requirements [9]. system tries to combine the benefts of a fxed system and a On the most limited fexibility level, systems have been fully fexible DRT. Furthermore, a memetic algorithm is proposed with fxed bus stops, routes, and timetables, but designed for optimizing the performance of this new system which run only when a booking is made. On the other end of when serving a set of registered requests. After evaluating the the spectrum, a fully fexible system operates without pre- performance of the algorithm, the performance of the determined bus stops, routes, or timetables, serving users in system is analyzed and compared to the performance of a a service resembling that of a taxi. Tese fully fexible systems traditional feeder system. Tis allows determining under typically run using smaller vehicles, and routes are created which circumstances this new system should be considered according to passengers’ requests in a ridesharing format, in practice. with fxed or variable fares according to the travelled dis- Te related literature on public bus transportation tance and service availability. Some papers compare these systems is discussed in the next section, both for feeder fully fexible systems with other systems or traditional bus systems in general and for the DRFS. Te assumptions for systems using simulations [10–12]. Other papers focus on the DRFS proposed in this paper are described in Section developing guidelines for the operation and classifcation of 3. Te memetic algorithm is discussed in detail in Section these systems [13]. 4. Section 5 presents the results of the experiments. First, According to a recent and comprehensive survey and the efciency of the memetic algorithm is evaluated by classifcation of demand-responsive public bus systems [14], comparing its results with an optimal solution obtained our DRFS corresponds to a many-to-one, semifexible, stop- through a mathematical model. Ten, the DRFS is com- based, static demand responsive bus system. Tis means it is pared to the TFS. Several instances are generated, varying feeder line (“many-to-one”), with fxed stops (“stop-based”, the list of requests in each instance. Five diferent not “door-to-door”), but fexible routes and timetables Journal of Advanced Transportation 3 (“semi-fexible”), which are designed before the operation 3. Problem Statement starts (“static”). Moreover, with the objective of minimizing Tis section discusses the assumptions on the semifexible the passenger travel time, it takes the passengers’ perspec- demand-responsive feeder system (DRFS) and the required tive. Only a few of these systems have been considered before input data. Te starting point is a traditional feeder system [15, 16], but they consider systems with a completely dif- (TFS) operating a fxed number of bus lines with standard ferent design. routes and a regular timetable in a suburban area. Tis Still, other semifexible feeder services, combining system is optimized for the average daily demand. characteristics of both the traditional and demand-re- Te DRFS is designed to replace the TFS during of-peak sponsive systems, can be found in the literature. For ex- hours and will modify the standard route for each bus line ample, a customized bus (CB) ofers a regular operation towards the hub station and the departure time of the optimized to passengers’ requests, determining routes scheduled buses based on passenger requests. For every according to the pick-up and drop-of locations of pas- operation period of the problem, a list of passenger requests sengers. Te operation is adjusted on a daily basis, based on is available. Each request represents a trip by a passenger, the clustering of demand in the service area [17–19]. A with a desired bus stop and preferred departure time to start demand-responsive connector (DRC) operates a fully fex- the trip. Te standard route of each bus line can be modifed ible door-to-hub service in cycles [20]. However, the cost of with one or more shortcuts and limited detours. With such taxi-like or shuttle transit mode requires large cities “limited detours,” we mean that in each detour at most two with dense populations for a proftable operation [21]. additional stops can be visited before returning back to the Te resulting system from merging a demand-responsive standard route. Tis assumption guarantees, on the one and a traditional system can generate a substitute for the hand, that lines are still similar to the standard lines, and on traditional system or a complementary system running in the other hand, that sufcient opportunities are available for parallel. Nourbakhsh and Ouyang [22] explore a fexible shortcuts to skip bus stops without passengers and making service for low-demand areas, ofering a door-to-door ser- detours when appropriate. For the purpose of limiting the vice that substitutes the traditional operation. Tis system, fexibility in this study, the value was set to at most two however, is applied only for a grid network. In another additional stops per detour, creating a balance between a complementary system for high-demand areas with a grid fully fexible DRFS and the TFS with fxed lines. Tis value, structure, Uchimura et al. [23] design a hierarchical struc- however, could be infuenced by several other factors in ture. On the upper level, traditional mass transit lines reality, such as the availability of an alternative route be- connect diferent areas with an express service. Te inter- tween stops, or the ability to visit multiple diferent stops mediate layer operates an intercommunity traditional transit with only a small detour. Tis results in a limited pool of system ofering hub stations where passengers can switch to possible routes for each bus line. the last layer, which is the intracommunity service designed Figure 1 presents an example of the DRFS operation. As as a fully fexible door-to-door demand-responsive system. in the traditional system, a bus line is indicated by a unique Only a few of these systems could be used as a replacement nomenclature (a number, a code, or a color, for instance) system in low demand areas. and this nomenclature is used by passengers to identify the Another aspect taken in account for semifexible services bus line they need to their destination. In Figure 1, the is the way to structure the routes for the buses. Pratelli et al. standard line of the TFS is indicated as a solid line, with bus [24] design a demand-responsive feeder system were part of stops 6, 5, 4, 1, and the last stop S. In the DRFS, it can be the stops are fxed, as in the traditional system, but the decided, before the operation starts, to include the dashed demand-responsive operation allows deviations to include a detour, picking up passengers at stops 3 and 2 and skipping limited number of extra requests from optional stops. A stops 5 and 4. Tis result in two possible routes for this line: methodology to choose the most suitable policy is defned the standard line and the line with the dashed detour. according to the level of demand and the accommodation rate [15]. In our semifexible DRFS, the structure of the lines from the traditional feeder system are kept, such as a fxed 3.1.AssumptionsfortheDRFS. Te DRFS runs in a suburban terminal to begin the service and a common destination for area represented by a graph G � {V, E}, where V is the set of all requests. Limited fexibility from this original line allows bus stops (i � 0, 1, . . . , n), and i � 0 representing the hub optimizing the operation in of-peak hours considering the station. Edges E indicate links between bus stops i ∈ V and preferred departure time of the passengers. j ∈ V at a travel cost of c . Some initial assumptions for the i,j To conclude, our DRFS operates in suburban areas as a operation are as follows: many-to-one, semifexible, stop-based, static demand re- sponsive bus system, in order to substitute a traditional (i) Te objective of the DRFS is to minimize the total system in of-peak hours. Terefore, it keeps the traditional travel time of the passengers; feeder systems’ structure but includes fexibility in order to (ii) Te service operates for n consecutive periods; allow passengers to request a trip to the hub station at their (iii) Tere are a fxed number of lines connecting all the preferred departure time. Mainly, the aspects that it is a bus stops to the hub station; semifexible system and that it operates in of-peak hours making it diferent compared to other systems in the state of (iv) All lines start at a predefned terminal bus stop and the art. head to the hub station; 4 Journal of Advanced Transportation equation is the diference between drop-of at the hub station and the preferred departure time: p � p + p � p − p + p − p � p − p . (1) 􏼐 􏼑 􏼐 􏼑 tt wt vt p r d p d r In order to determine the penalty for a rejected request, it is assumed that passengers will be waiting for a bus until the next operation period. Since the routes for the next period are not defned yet, and since all buses depart from the terminal and arrive at the station within the operation period, it means that, in the worst case, rejected requests will arrive at the station by the end of the following operation period. Terefore, a passenger penalization (p ) is given by pen the time diference between the passengers’ preferred de- parture time and the end of the following operation period given by the following equation: p � 􏼐p − p 􏼑 + p � 2 ∗ p − p . (2) pen op r op op r Figure 1: Example of a line with two routes for the DRFS. 3.2. Generation of the Pool of Routes for the Lines. Te (v) Each bus is associated with a line, following a problem formulation of the DRFS uses a limited pool of route from the pool of routes generated for that alternative routes for each bus. In this subsection, we de- line; velop a method to generate such a pool. Te proposed (vi) Te pool of routes includes all feasible routes for semifexible DRFS focuses on operating a fexible service but each line, considering stop skipping and limited keeping the main characteristics of the TFS. Terefore, we detours; start from the standard (TFS) route of each line and then (vii) Te route length is limited to the duration of the generate a set of alternative routes using “stop skipping” and operation period (p ); op “limited detours.” (viii) Te buses depart from the terminal and arrive at Te standard routes are optimally designed for the TFS, the hub station within the operation period; serving all bus stops and efciently accommodating all the demand over multiple periods. In the DRFS, buses do not (ix) Te departure times of the buses are not fxed but follow these standard routes, but decide for the best route can be adjusted within the operation period; according to the requests for each operation period. Stop (x) Te bus capacity is assumed to be sufcient to skipping and limited detours are considered. Stop skipping address all requests. means that it is possible to skip one or a sequence of bus For each period of operation, there is a list of requests stops in the standard route. Detours mean that it is possible to include additional bus stops in the standard route. Since representing passengers that want to use the service during that period. Each request is composed of an origin bus stop the DRFS is not a fully fexible system where buses are and a preferred departure time (p allowed to take any possible route, we limit the detours to ) representing the mo- ment a passenger will be ready to take the bus towards the including at most two other bus stops before returning to a hub station. A request can be accepted or rejected. If ac- bus stop in the standard line. However, it is possible to cepted, it means that this passenger will be picked up by one combine detours with stop skipping. Furthermore, cycles are of the buses in that operation period at pick-up time (p ) not allowed, which means that a bus stop cannot be visited and will reach the station at drop-of time (p ). If a request is twice by the same bus. Moreover, a limit is set on the rejected, it means no bus will pass by the passenger’s bus stop maximum route length to control the maximum travel time after its preferred departure time, and a penalty will be a bus can ride. It should be noted that overlaps between associated with this request. Rejected requests are then in- diferent lines are possible, resulting in more than one line serving the same bus stop. cluded in the request list for the following operation period. After the last optimized of-peak period, it is assumed that By considering the limited detours, it is possible to precalculate all possible routes for each line in the DRFS. again the TFS is operated, serving all stops. Terefore, all passengers will be served. Tese alternative routes are then stored in a pool of routes Te main objective of the DRFS is to minimize the that are used by the memetic algorithm instead of recal- passenger total travel time (p ) by selecting, in each period, culating all possible movements while exploring solutions tt the best route and best departure time for each bus. Te total for the routes. As an example, Figures 2 and 3 illustrate a TFS travel time consists of the passenger waiting time (p ) at the operation in a grid network composed of nine bus stops and wt bus stop and the passenger in-vehicle time (p ) until a station S, served by a red line (Figure 2) and a blue line vt passengers arrive at the hub station. Terefore, the total (Figure 3). Figures 2 and 3 also indicate the possible detours travel time for each passenger given in the following or stop skipping for these lines, based on the previously Journal of Advanced Transportation 5 stated assumptions. For instance, the original route of the blue line includes the sequence of stops 9-8-7-4-1-0. When 3 6 9 the bus arrive at the stop number 8, it is possible to include a detour to stop number 5 instead of continuing the initial route to stop 7. From this point, the bus can return to the 2 5 8 original line, visiting stop number 4 and skipping the bus stop number 7, or include another detour to visit stop number 2. After this second detour, the bus is obliged to return to the original line. Te stop 3 cannot be included in 1 4 7 the blue route since it would require a detour of more than 100 two stops to return to the standard route. Tat is, from stop 9, it would require a detour to stop number 6 and then to stop number 3, but then it would require at least one more stop to return to the original line, which is not allowed. 0 100 200 300 Figure 2: Red line for a TFS operating a grid network and allowed 3.3. List of Requests and Operation Period. Every passenger detours and stop skipping. that wishes to use the system submits a request composed of a bus stop and a preferred departure time. It means pas- sengers are planning to arrive at the given bus stop and will be waiting for the bus from that moment on. Since the of- peak operation is divided in periods of operation, requests 36 9 have to be submitted before the start of the corresponding operation period. Once the buses of an operation period start running, no new requests for that operation period are 2 5 8 allowed. Terefore, the requests considered for the opti- mization of an operation period are those related to that operation period and unserved requests from previous operation periods. 1 4 7 4. Memetic Algorithm Approach Optimizing the performance of the DRFS discussed in the previous section is addressed with a memetic algorithm 0 100 200 300 (MA), combining an evolutionary heuristic suitable for Figure 3: Blue line for a TFS operating a grid network and allowed exploring large areas of the search space in coordination detours and stop skipping. with repair and improvement functions, acting as local search techniques, to improve solutions to ft the preferred period begins and takes a shortcut straight to bus stop 2, departure time of passengers. Te framework of the pro- posed MA uses diferent iterations to confgure the buses’ where the standard route is followed until the station. operation, i.e., route assignment and departure time for each bus. An overview of the MA is presented in Algorithm 1. 4.1. Population Generation. Te MA approach aims to Figure 4 illustrates the fowchart of the MA. For each identify, for each operation period, the solution that min- period of operation, the requests received for that period, the imizes the total passenger travel time. Te frst step of the rejected requests from previous periods and the list of MA is to populate the initial generation with solutions. Since possible routes for each line are considered as input. Sub- all buses must arrive at the station before the end of the sequently, a generation with initial solutions is created and operation period, the route length determines the maximum the ftness value for each solution is calculated. Ten, the delay time a bus can have. Terefore, the route is assigned process of selection, crossover, mutation, repair, and im- frst; selecting a random route from the pool of routes for provement is repeated until a given number of generations is each line, and then, a departure time is assigned randomly produced without further improvement of the best solution. limited to the maximum delay time. Tis random generation For each operation period in the operation horizon, a tries to cover a large number of possible combinations of solution is represented by a list of bus stops and a departure routes and departure times as possible, which are then time from the terminal for each bus line of the service. Te subjected to further improvements in the following route is represented by a sequence of bus stops and the generations. departure time with a delay from the beginning of the operation period. For instance, a possible representation for the red line service on Figure 2 could be the route that 4.2. Evaluation of Solutions. After assigning a route and a departs from the terminal 20 minutes after the operation departure time to each line of the operation period, it is 6 Journal of Advanced Transportation Start: For each line in set of line: Initialize pool of possible routes for line Append requests of the current operation period in the list of requests Append rejected requests from previous periods in the list of requests Generate n initial solutions Identify the list of 5% best solutions Repeat: Create a new empty generation Add the 5% best solutions from previous generation Repeat: Generate two new solutions with crossover operation Apply mutation on these two solutions Evaluate solutions Until solutions in the new generation � n Apply repair operation to all solutions Apply improvement operation to all solutions Update list of 5% best solutions Until termination criteria ALGORITHM 1: MA full algorithm pseudo-code. possible to generate the timetable for all bus stops and the Start arrival time of the buses at the station. Tis information is used to evaluate the objective function value of the solution using the list of requests for the current operation period. List of requests Te ftness of a solution is given by the sum of passenger travel time for all requests in the list of requests (r ∈ R) as Pool of follows: routes Objective function value � 􏽘 p + p . tt pen (3) r∈R Initialization For every request in the list of requests, the passengers’ preferred departure time (p ) is compared with the time- table for that bus stop. If a passenger arrives at the bus stop Fitness calculation before the bus, the request is accepted and p and p are p d updated. If the passenger arrives at the bus stop after the bus passed by, or no bus visits the stop in that operation period, the request is penalized, and this request is included in the Yes Termination list of requests for the next operation period. If more than criteria one bus from diferent lines can serve a passenger in the same operation period, the one that arrives earlier at the No station is chosen. It should be noted that this is not nec- essarily the frst bus serving the stop. Selection After evaluating the new solutions in a generation, they are sorted according to the ftness value, and the solution with the smallest ftness is set as the best solution of the generation. Also, the top 5% of the solutions are set as good Crossover/Mutation solutions for the elitist crossover method (below). If the population size is smaller than 100 solutions, at least fve solutions are set as good solutions. Te evaluation ftness function is presented in Algorithm 2. Repair/Improvement 4.3. Crossover Operation. Te frst operation to populate new generations is the crossover. Te MA uses two diferent End methods: an elitist and a random crossover, with a proba- Figure 4: Flowchart of the memetic algorithm. bility of 50% each. In the elitist method, at least one of the Journal of Advanced Transportation 7 Start: Solution ftness � 0 For request in list of requests: If preferred departure time at request stop≤ bus arrival at request stop: p � time bus arrive at bus stop p � time bus arrive at station p � p − p tt d r Solution ftness + � p tt Else: p � 2 ∗ p − p pen op r Solution ftness + � p pen Return Solution ftness ALGORITHM 2: Fitness evaluation. parents is selected from the group of good solutions. Te to be served on one of the lines. If the request is rejected due other parent is randomly selected. In the random crossover, to early service, the repair function tries to delay the cor- both parents are selected randomly from the general pop- responding bus as much as possible, so the bus arrives at the ulation. Once the parents are selected, the crossover selects bus stop at the same time as the passenger. It consequently the routes of the lines and the departure time from the delays all arrival times for all the bus stops in the route and parents to generate two new solutions. It is done by ran- thus increases the waiting times for other passengers. Ob- domly assigning to each line of one new solution, the route viously, this delay is limited by the fact that the bus should and departure time used by a randomly selected parent on arrive at the hub station before the end of the operation period. this line. Te nonselected route (and departure time) for that line is then assigned to the second new solution. Te A more complex procedure is executed if the request is crossover operation is presented in Algorithm 3. rejected due to an unserved bus stop. First, one of the possible lines that may serve the bus stop is selected. In the example of Figures 2 and 3, for instance, bus stop three can 4.4. Mutation Operation. Te mutation operation includes only be served by the red line, bus stop seven only by the blue variability in the generations by changing routes and de- line, and all the others bus stops by both lines. Second, parture times of a solution after the crossover method, with a considering the current route for the selected line, all bus 5% probability of occurring. A mutation can be a small or a stops where passengers are being served by this route are large mutation, each with a 50% probability. In the small marked, and a new route including all these marked bus mutation, one route and departure time of the solution is stops and the bus stop of the rejected request is chosen from randomly modifed. In the large mutation, all routes and the pool of routes for this line. Finally, the procedure checks departure times are generated again for that solution, whether the departure time needs to be adjusted, either resulting in a completely new solution. Tese new solutions because the new route is longer than the previous or because are introduced to stimulate diversifcation in the population. the arrival time at the included bus stop is still not serving After the mutation operation, the new solution is included in the penalized request. the new generation list, whether mutated or not. Te mu- An example of this procedure is illustrated in Figure 5. In tation operation is presented in Algorithm 4. this example, there is a penalized request at bus stop four, not served by neither the red line (a) nor the blue line (b), 4.5. Repair Operation. After populating the new generation, since this bus stop can be included in both the lines, stops with served passengers on the current route of the lines are all solutions pass through both the repair and the im- provement operations. Te repair operation modifes the marked: stops 8 and 1, if the red line is chosen, and stops 8 and 2 for the blue line. Tere are no possible routes including solution, trying to avoid penalized requests and accepting them in the current period. First, all rejected requests in the the stops 8, 4, and 1 in the same route for the red line, list of requests are categorized according to the type of therefore, this option is discarded. For the blue line, it is penalty, i.e., whether the penalty results from an early bus possible to change the route to the sequence illustrated on service or from an unserved bus stop. An early bus service Figure 5(c). Te last check adjusts the departure time for the means a passenger arrives at the requested bus stop after the optimized request. Te bus in the blue line departs at the last bus has already served that bus stop, and consequently, beginning of the operation period. It will serve bus stop 4, this passenger is not served. In the case of an unserved bus 15 minutes later with the new route. If the passenger arrives stop, the bus stop is not visited by any bus in the current any time earlier, there will be no adjustment in the departure time of the bus. If the passenger arrives later, the departure solution, and passengers requesting travel from these stops are forced to wait for the next period. time of the bus will be delayed as much as possible, so this passenger does not have to wait for the bus, respecting the Once all penalized requests are categorized, one of them is randomly selected to be “repaired” by forcing this request maximum arrival time at the station. 8 Journal of Advanced Transportation Start: Random selection of crossover method: elitist or random If elitist: Choose random parent (P ) from the list of best solutions If random: Choose random parent (P ) from previous generation Choose second random parent (P ) from previous generation Create empty ofspring -> O , O 1 2 For line in set of lines: Random selection order: true or false If true: O receives line confguration from P 1 1 O receives line confguration from P 2 2 If false: O receives line confguration from P 1 2 O receives line confguration from P 2 1 ReturnO , O 1 2 ALGORITHM 3: Crossover operation. Start: mutation probability � Random number between (0, 100) If mutation probability≤ 5: Choose mutation size: small or large If small: Choose a random line from solution Select a random route in the pool of routes for this line max departure time � operation period time–route length bus departure � random time between (0, max departure time) If large: For each line in set of lines: Select a random route in the pool of routes for this line max departure time � operation period time–route length bus departure � random time between (0, max departure time) Return Solution ALGORITHM 4: Mutation operation for new solutions. Departure: +18′ Departure: +0′ Departure: +0′ 8 2 8 2 8 14 4 4 (a) (b) (c) Figure 5: Example of a repair operation for a small grid network to include a request in bus stop 4 in the red or the blue line: (a) the current red line with passengers at stops 8 and 1; (b) the current blue line with passengers at stops 8 and 2; (c) fnal solution adapting the blue line. Journal of Advanced Transportation 9 After fnishing the repair operation, the new solution is created. In these instances, buses are allowed to take any re-evaluated, and if the ftness is improved compared to the route in the network from terminal to station. Finally, the previous one, the new repaired solution replaces the earlier MA is evaluated on larger instances, with 70 bus stops in the solution in the new generation. Otherwise, it is discarded. area instead of 25 bus stops. Tese two last experiments allow evaluating the viability of the MA to fnd local optima for complex instances and to check the performance of the 4.6. Improvement Operation. Te last operation included in DRFS. the MA is the improvement operation. While the repair operation tries to delay the departure time of buses or to 5.1. Network and Instances. Since this DRFS was not studied include stops not served in the routes, the improvement before, there are no benchmark instances available to operation advances the departure time of a bus or makes the evaluate the performance of the MA. Terefore, new in- route more direct to the destination. Te operation starts stances are created based on a graph corresponding to a with the selection of a random request from the list of suburban area served with a feeder bus system. It is com- accepted requests. After checking which bus is currently posed of 25 bus stops connected to a transfer station (S) and serving the request, two steps are executed. First, it tries to served by three lines. All lines start at bus stop/terminal 25. fnd a new route aiming to reduce the in-vehicle time for the Each bus stop expects 1 to 6 passengers, with a total of 100 passenger of this request. As in the previous operation, all requests over fve consecutive operation periods. Te time a bus stops serving passengers along the current route are bus takes from one bus stop to another is equivalent to the marked. Ten, a new route is selected for this line only when Euclidian distance between the bus stops, converted to there is a shorter route for the selected request with all the minutes, and presented in Figure 7. Te length for the marked bus stops along the route. Second, the bus departure standard lines for the TFS and the number of alternative is set earlier as much as possible to reduce the waiting time routes in the pool of routes for each line in the DRFS are for this request. Te new solution replaces the earlier one in presented in Table 1. Te lines for the TFS are optimized to the new generation if the improvement operation improves serve the total demand presented in Table 2. Tese lines are ftness. obtained with an exact optimization approach developed for Te operation of the improvement function is illustrated the bus line planning problem considering the average daily in Figure 6. In this example, there is a request for bus stop 2 demand expected at the diferent bus stops [25]. Te ob- with the preferred departure time 30 minutes after the pe- jective is to minimize the passenger travel time from the riod starts, and this passenger is served with a bus from the diferent bus stops to the hub station. It results in the optimal blue line following route illustrated on the left in Figure 6. standard routes for the lines of the TFS. In a second step, the Te current departure time from the terminal is 25 minutes frequency of the service is set to one bus per line per op- after the beginning of the period, and the bus is picking up eration period. Tis procedure is similar to the planning of the selected passenger at time 40. Terefore, the waiting time traditional feeder systems in practice. for this passenger is 10 minutes. In the improved solution, One instance with fve operation periods is shown in on the right in Figure 6, the route is kept unchanged since Table 3. In each operation period of this example, requests there is no route in the pool of routes with a shorter in- are concentrated in 9 to 15 diferent bus stops of the 25, vehicle time from bus stop 2 to the station. Ten, the bus is corresponding to, on average, half of the bus stops per set to depart 10 minutes earlier, consequently arriving earlier operation period. Tis means that in the total operation at every bus stop along the way and picking up the passenger horizon, there are 50% of stops without requests (50% of at bus stop 2 without any waiting time. If other passengers empty bus stops). Several instances with random distribu- are being served by this bus, there are two options: their tions of demand were created, categorized according to the waiting times are reduced by 10 minutes, or their requests number of empty bus stops in the total operation: 30%, 50%, are rejected in this solution. After updating the route and the or 70%. timetable, the new solution is re-evaluated, and if the ftness is better, the new solution replaces the earlier one in the new generation. Otherwise, it is discarded. 5.2. Sensitivity Analyses forMA’s Parameters. Tis sensitivity analysis examines the parameters for the MA, i.e., the size of the population in each generation and the stop criteria in the 5. Results search for improvements. In order to somewhat limit the In this section, results for the MA are presented in six computation time required to optimize an operation period, population sizes of 50, 100, or 200 are considered combined analyses: First, benchmark instances for the DRFS are created and the parameters of the MA are evaluated in a with a maximum number of generations without im- sensitivity analysis. Te MA is then validated through a provements of 20, 50, or 100. Beyond these parameters, the comparison with a mathematical model that solves a very total number of generations was limited to 1.000. During the similar but somewhat easier problem to optimality. Second, experiments reported in this paper, however, this value was the MA solutions for the benchmark instances are compared never reached. with those of a TFS. Tird, instances are generated with Te results for this sensitivity analysis are presented in Table 4 for 15 instances grouped in three categories variations in the number of lines. Fourth, more complex instances without restriction on the possible detours are according to the percentage of empty stops (30%, 50%, and 10 Journal of Advanced Transportation Stop 2, Dep. time: +40’ Stop 2, Dep. time: +30’ Request for stop 2 Request for stop 2 p = 10ʹ p = 0ʹ w at time: + 30’ at time: + 30’ Figure 6: Illustration of improvement operation for a request and the improved line, advancing the departure time of the bus 10 minutes to reduce the waiting time of this passenger. Table 2: Expected demand for each bus stop during the entire 5 15 operation horizon. Stops Demands 1 1 2 4 4 9 3 6 4 1 5 4 6 4 7 2 8 6 9 6 10 4 11 1 12 6 13 6 14 2 15 6 16 4 17 6 18 6 S 100 200 300 400 500 19 4 20 6 Figure 7: Network representing a suburban area, served by three 21 4 lines in a TFS. 22 4 23 1 24 2 25 4 Table 1: Network characteristics: length of lines for the standard route in the TFS; number of routes in the pool of routes for each line in the operation period. considering the quality of the results, we conclude that a Lines Route lengths (min) Pool of routes size population size of 100 solutions and a stop criteria of 50 generations without improvements are appropriate param- Red 32.1 192 Green 33.2 60 eter values, increasing the population size from 100 to 200 or Blue 28.2 225 the maximum number of generations without improvement Combinations of routes: 2.592.000 from 50 to 100 produced the same passenger travel time on average (31.8 min) for these 15 instances, but the computation Operation period duration: 60 min time increased from 55 to 126 and 132 seconds, respectively. Reducing these parameters increased the optimal value of the 70%), with fve instances for each group. Te results present solutions. We conclude that the selected parameters values the average passenger travel time in minutes, and the com- guarantee (at least for these instances) a reasonable number of putation time in seconds. Considering the limited available generations before reaching the stop criterion and sufcient time for computations just before each operation period, and diversity in the population. Stop 9, Dep. time: +25’ Stop 8, Dep. time: +30’ Stop 5, Dep. time: +35’ Stop 1, Dep. time: +45’ Station S, Dep. time: +55’ Stop 9, Dep. time: +15’ Stop 8, Dep. time: +20’ Stop 5, Dep. time: +25’ Stop 1, Dep. time: +35’ Station S, Dep. time: +45’ Journal of Advanced Transportation 11 Table 3: Example of demand distribution in the operation horizon, corresponding to fve operation periods. Bus stops Requests Stops w/o Empty per requests stops (%) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 period 1st 0 2 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 2 0 0 0 0 0 1 0 11 16 64.00 2nd 1 2 0 1 0 2 0 1 3 2 0 1 1 0 0 2 2 1 1 0 0 0 1 0 2 23 10 40.00 Op. 3rd 0 0 3 0 2 0 0 2 1 0 0 2 2 0 2 0 2 0 2 0 2 0 0 0 0 20 15 60.00 Period 4th 0 0 2 0 1 0 0 2 1 1 0 2 2 2 1 0 2 3 1 0 2 3 0 0 1 26 10 40.00 5th 0 0 1 0 1 1 1 1 0 1 1 0 0 0 3 1 0 0 0 6 0 1 0 1 1 20 12 48.00 Sum of 1 4 6 1 4 4 2 6 6 4 1 6 6 2 6 4 6 6 4 6 4 4 1 2 4 100 63 50.00 demand Table 4: Sensitivity analysis of the MA for a population of 50, 100, or 200 solutions and the stop condition without improvements of the best solution for 20, 50, and 100 iterations. Results show the passenger travel time (t.t.) and the computation time (CPU). Max. number of iterations without improvements 20 50 100 Population sizes t.t. (min) CPU (s) t.t. (min) CPU (s) t.t. (min) CPU (s) 30% 33.5 18 33.8 34 33.2 69 50% 31.7 16 31.7 38 31.1 64 70% 31.3 17 31.4 34 31.2 63 Avg 32.2 17 32.3 36 31.8 66 30% 33.7 29 33.4 60 33.1 128 50% 31.4 29 31.1 54 31.3 125 70% 31.1 29 30.9 52 31 143 Avg 32.1 29 31.8 55 31.8 132 30% 33.4 57 33.4 122 32.8 249 50% 31 58 31.3 118 30.8 193 70% 30.4 62 30.7 138 30.7 242 Avg 31.6 59 31.8 126 31.4 228 optimization for the DRFS. Te routes for the demand il- 5.3. Performance of the MA. Tis frst analysis evaluates the performance of the MA by comparing its solutions with the lustrated in Table 3 are shown in Figure 8 as an example for optimal solutions obtained with the exact model of a similar the three solutions (TFS and optimal solution and MA problem solved with CPLEX. In this model, buses depart at solution for the DRFS) on all fve operation periods. Buses the beginning of the operation period for all lines, and no depart at the beginning of the operation period for all lines in exact arrival times of passengers at the bus stops are con- the TFS and in the optimal solution for the DRFS, due to the sidered. Instead, all passengers are assumed to be present at initial assumptions. In the solution found by the MA for the the bus stop at the beginning of each operation period. DRFS, the departure times identifed by the algorithm were Terefore, in all instances considered in this subsection, all also equal to the beginning of the operation period for all preferred departure times are set equal to the beginning of lines. the operation period. Tis also implies that all passengers are For this analysis, data for twenty operation horizons were randomly generated for each percentage of empty served in the operation period for which they submitted a request, and the preferred departure time is always zero. Due stops, and with fve operation periods each. Terefore, 300 to this simplifcation, the model can be solved to optimality operation periods are optimized both with the mathematical for the size of instances considered. Te model is presented model in CPLEX and using the MA. Both waiting and in- and discussed in Appendix A (available here). vehicle times of passengers are evaluated, considering the For this analysis, data for twenty operation horizons standard routes for the TFS, and the optimal routes obtained were randomly generated for each percentage of empty by CPLEX, and the routes obtained with the MA optimi- stops, and with fve operation periods each. Terefore, 300 zation for the DRFS. Te routes for the demand illustrated in operation periods are optimized both with the mathematical Table 3 are shown in Figure 8 as an example for the three solutions (TFS and optimal solution and MA solution for the model in CPLEX and using the MA. Both waiting and in- vehicle times of passengers are evaluated, considering the DRFS) on all fve operation periods. Buses depart at the standard routes for the TFS, and the optimal routes obtained beginning of the operation period for all lines in the TFS and by CPLEX, and the routes obtained with the MA in the optimal solution for the DRFS, due to the initial 12 Journal of Advanced Transportation DRFS – Mathematical TFS DRFS – Memetic Algorithm model 500 500 500 400 400 300 300 200 200 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 200 100 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 200 100 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 200 100 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 100 100 0 0 0 200 400 0 200 400 0 200 400 st nd Figure 8: Routes for total operation in the TFS (1 column), the optimal solution obtained with the mathematical model for the DRFS (2 rd column), and the solution obtained for the DRFS with the MA (3 column) for all the fve operation periods of one instance. 5th Period 4th Period 3rd Period 2nd Period 1st Period 5th Period 4th Period 3rd Period 2nd Period 1st Period 5th Period 4th Period 3rd Period 2nd Period 1st Period Journal of Advanced Transportation 13 comparison with results obtained by solving the mathe- assumptions. In the solution found by the MA for the DRFS, the departure times identifed by the algorithm were also matical model. In this second part of the analysis, the de- mand distribution over the diferent stops is the same as equal to the beginning of the operation period for all lines. As mentioned before, routes are identical for all oper- before for the 60 instances, but the preferred departure time ation periods in the TFS. Six routes in the optimal DRFS can take any value within the operation period. Tis means solution are the same as in the TFS. It happens in the frst that some preferred departure times occur after the bus has three operation periods for the red line and in the frst, already served the respective bus stop, and these passengers second, and ffth period for the green line. Eleven out of are left to be served in the following operation period. Tis ffteen routes for the lines in the DRFS obtained with the MA results in a variation in the average passenger waiting time, even for the TFS. For the demand presented in Table 3, the are identical to the optimal DRFS solution. All routes ob- tained with the MA solution were identical to the optimal MA solution for the third operation period is illustrated in Figure 9, as an example. For this solution, the bus in the blue solution for the frst and ffth operation periods. Tere are slight variations in the routes obtained for the second and line departs two minutes after the operation period begins, at time 02 : 02, and arrives at the station at 02 : 35. Te bus in the fourth period. Te average passenger travel time for this instance is presented in Table 5 for each operation period. the green line departs at 02 :17, and arrives at the station at For the TFS, the average passenger travel time was 31.5 min. 02 : 55. Te red line bus departs at 02 :19, arriving at 02 : 53, For the DRFS, this value was 10.8% lower with the optimal 7 minutes before 03 : 00, the end of the period. Buses pick up solution, representing a reduction of 3.4 minutes. For the passengers in the bus stops marked in the fgure. Results for solution obtained with the MA, the average passenger travel this instance and routes for the fve operation periods in the time was 0.1 minutes longer than the optimal solution. MA solution are presented in Appendix B, together with the full table with the scheduled departure time for each pas- Te optimal travel time for passengers was achieved in four out of fve optimized periods with the MA. As men- senger for this operation period. tioned before, the MA found identical routes as in the optimal solution for the frst and the last operation periods, 5.4. Results of the MA for General Instances. Te results for so both simulations present the same results. For the second the MA are compared to the TFS for all the 60 instances, and the fourth operation periods, even though routes were grouped by the percentage of empty stops, and presented in not the same for all the lines as in the optimal solution, the Table 7. Tis table shows the average passenger waiting, in- obtained results with the MA were the same as the optimal vehicle, and total travel time for the TFS and the DRFS with result. It means that diferent routes serve passengers with the MA solution. On average, the time passengers spend on the same efciency as in the optimal solutions. Passengers in the bus in the optimal routes of the DRFS is slightly in- the third period had an average travel time of 29 minutes creased compared to the time passengers took while trav- with the solution of the MA, a value 2.5% above the optimal eling using standard routes in the TFS. However, this value solution. decreases the more empty stops are present in the instances. Tis same analysis was repeated for all 60 instances, It means that detours included in the lines’ routes to serve comparing the average passenger travel time for the TFS, passengers increase the average in-vehicle time, but skipping and the optimal and the MA solution for the DRFS (Table 6). empty bus stops can reduce it. On the other hand, the av- In the optimal solutions, the average passenger travel time erage passenger waiting time on the DRFS reduced by 48.1% was 8.6% shorter than the TFS solution, while the MA could compared to the TFS, with an overall improvement of 30.6% improve the passenger travel time by 8.0%. Moreover, the on passenger travel time. However, since the memetic al- results of the MA were the same as in the optimal solution in gorithm’s objective is to improve passenger travel times, the 69.3% of the operation periods. Increasing the percentage of routes taken by buses while not carrying passengers are not empty stops does not make any diference in passenger travel always the shortest route possible. Tis does not imply that time on TFS because routes for the lines are identical for the these solutions can be further improved, because bus driving whole operation period. In the optimal and the MA solutions time is not part of the objective function and the buses are for the DRFS, however, increasing the percentage of empty optimally serving passengers. Te average calculation time to bus stops in the instances allows the possibility to skip empty achieve the termination criteria for the MA was 56 seconds bus stops and serve busy bus stops faster. With 30% empty per operation period. stops, passenger travel time was 1.3 minutes shorter in the optimal solutions than in the TFS. With 70% of empty stops, this value was 4.5 minutes shorter. On average, passengers 5.5. Results of the MA for Varying Numbers of Lines. Te could arrive at the station 2.7 min earlier if the routes of the previous analyses consisted of a network with three lines. In TFS could be adapted and changed dynamically. Comparing this section, the same network with the same demand is now computation times for these simplifed instances, the served by a system with two and four lines instead of three, in order to analyze the impact of that parameter. To make a fair mathematical models took 6.5 seconds on average to identify the optimal solution for each period of operation, and the comparison with the TFS, the lines of the traditional feeder system are optimized using the MA, considering the total MA took 52 seconds on average. In the previous analysis, passengers requested their trips demand for entire operation horizon both for two and four to start exactly at the beginning of the operation period, in lines. Te standard lines for the TFS services for two and four order to generate a simplifed problem, allowing the lines are presented in Appendix C. 14 Journal of Advanced Transportation Table 5: Average p for each period of the example simulated. tt MA solution Periods TFS solution (min) Optimal solution (min) (min) 1st 31 28.3 28.3 2nd 30.9 29.4 29.4 3rd 31.8 28.3 29 4th 32.4 27.1 27.1 5th 31.3 27.4 27.4 Average 31.5 28.1 28.2 Table 6: Average passenger travel time in the TFS, with optimal routes and the MA. Improvement of optimal and MA solution compared to TFS, classifed according to the percentage of empty bus stops in the instance. TFS solution Optimal solution Optimal solution improvement MA solution MA solution improvement (min) (min) (%) (min) (%) 30% empty 31.5 30.2 4.2 30.5 3.2 stops 50% empty 31.5 29.1 7.6 29.3 7.1 stops 70% empty 31.5 27.0 14.1 27.2 13.7 stops Average 31.5 28.8 8.6 29.0 8.0 Departure:+19ʹ Departure:+17ʹ Departure:+2ʹ 0 100 200 300 400 500 0 100 200 300 400 500 0 100 200 300 400 500 Figure 9: Example of MA solution for the third operation period with 50% of empty stops. and four lines is that the area considered can be covered Table 7: Results of average passenger waiting, in-vehicle, and total easily with only three lines and therefore all three (or four) travel times for the TFS and the MA grouped by percentage of empty stops in the instances. lines have a length close to the minimal travel time between the terminal and the hub station. With only two lines, longer TFS solution MA solution Improvement lines are required to cover the area. Terefore passengers p p p p p p p (%) wt vt tt wt vt tt tt have to wait longer for their buses and spend more time 30% empty inside the vehicles before reaching the hub station. Tese 29.1 16.5 45.6 15.9 16.9 32.8 28.20 stops results are presented in the frst columns of Table 8. 50% empty When there are four buses in the semifexible DRFS, the 29.4 16.5 45.9 15.7 16.6 32.3 29.50 stops optimization adjusts better to the passengers’ expectations. 70% empty 30.5 16.5 47 14.7 16.4 31.1 34.00 On average, the passenger travel time in the DRFS is 37.6% stops shorter compared to the TFS, while this was 30.6% for three Average 29.7 16.5 46.2 15.4 16.6 32.1 30.60 lines and 29.8% for two lines on the DRFS. Te passenger waiting time reduced on average with 8.9, 14.3, and 16.8 minutes for two, three and four lines. On the other Te average lengths of the TFS lines with two, three, and hand, it is possible to identify a reduction in the in-vehicle four lines are 50.5, 31.2, and 29.3 minutes. Te reason why times of passengers for two lines only (7.9 minutes). For the average length of the lines are roughly the same for three three and four lines, the passenger in-vehicle times increased Journal of Advanced Transportation 15 Table 8: Average passenger waiting, in-vehicle, and travel time for 2 or 4 lines. TFS solution MA solution Improvement p p p p p p p (%) tt tt tt wt vt wt vt 30% empty stops 28.1 27.7 55.8 20.3 20.7 40.9 26.60 50% empty stops 28.4 27.7 56.1 20.2 19.8 40 28.60 2 lines 70% empty stops 28.8 27.7 56.5 18.1 19 37.1 34.30 Average 28.4 27.7 56.1 19.5 19.8 39.4 29.80 30% empty stops 29.1 16.5 45.6 15.9 16.9 32.8 28.20 50% empty stops 29.4 16.5 45.9 15.7 16.6 32.4 29.50 3 lines 70% empty stops 30.5 16.5 47 14.7 16.4 31 34.00 Average 29.7 16.5 46.2 15.4 16.6 32.1 30.60 30% empty stops 28.4 15.5 44 12.9 15.8 28.7 34.70 50% empty stops 29.1 15.5 44.7 12.1 15.7 27.9 37.60 4 lines 70% empty stops 29.8 15.5 45.3 11.7 15.3 27 40.40 Average 29.1 15.5 44.7 12.3 15.6 27.9 37.60 0.1 minutes. It means that more options for stop skipping to percentage of empty bus stops in the simulation reduced the shorten the routes are available with two lines. With three or in-vehicle time as well, and this gain is refected in the average passenger total travel time. From 32.1 min with four lines, detours optimize the passenger waiting time, but the average length of routes are roughly the same. limited detours, the average travel time obtained with the MA solution with unrestricted detours was reduced to Te average computation time per operation period was 53 seconds for the network with 4 lines, while in the network 31.5 min. Te average computation time for the optimiza- with two lines, the computation time was 93 seconds. Longer tions was 407 seconds. routes also mean a bigger search space for the MA, refected in the number of routes in the pool of alternative routes. 5.7. Large Network Instances. One last analysis considers a larger network with 70 bus stops and a centralized hub, and 5.6. Instances with Unrestricted Detours. So far, the possible 300 requests in fve operation periods. Te large network and the standard lines of the TFS are presented in Appendix detours that a bus could make were restricted to at most two bus stops from the original route. In this analysis, the same C. Here, again three lines are considered to serve the bus stops, with fxed terminal on bus stops 1, 63, and 70. In order instances are considered, but buses are allowed to take any possible route in the network. Tis will allow to further to identify the standard routes for the TFS, the MA was used analyze the performance of the MA and to evaluate the with the total demand for the entire operation horizon and opportunity of allowing more fexibility in the routes. Still, unrestricted detours for the lines were allowed. Tis pro- no cycles are allowed, and the route length is limited by the cedure does not guarantee the optimal routes for the lines as duration of the operation period. in the previous network but leads to a good solution given Te number of possible routes generated for the pool of the complexity of the network. Since routes are now much routes increases from 192 for the red line, 60 for the green, longer and the same numbers of buses are available, the and 225 for the blue line with at most two bus stops outside operation period considers a frequency of one bus every two hours. Terefore, for the DRFS, the routes were limited to the original route (Table 1), to 2,149 routes with unrestricted detours for each line. All possible combinations from the not exceed 120 minutes. All the other rules were kept as initially, considering the possibility of deviating from the terminal to the station are considered. Terefore, the search space increases from 2.6 million possible combinations to 10 standard route to include at most two extra bus stops or to billion. Beyond that, it is still necessary to identify the op- skip stops. Fifteen instances were optimized with this net- timal departure time for the buses considering preferred work, fve for each group according to the percentage of departure time for the requests. empty stops (30%, 50%, and 70%). As before, the variation Results for the same 60 instances as in the analysis in between instances occurs on the randomization of the Section 5.4 are presented in Table 9, comparing the solutions preferred departure time of passengers and the operation period on which the trip is requested. Results are presented obtained with the MA for the limited and unrestricted detours. Beyond the initial reduction in travel time observed in Table 10. Since the operation period is two hours and requests for the DRFS in comparison to the TFS, the value was further reduced by 1.7% with unrestricted detours. Te average arrive randomly in the instances, the average passenger waiting time in the TFS is 60.1 min. For this confguration of passenger waiting time reduced from 15.4 min with limited detours to 13.7 min, 11% shorter. Te in-vehicle time was a the network and instances, the MA could be able to reduce bit longer, on average 16.6 min per passenger compared to this waiting time by 21% to 47.2 min. Te in-vehicle time was 17.9 min with the limited detours (7.8% longer). An oper- reduced by 13%, from 41.0 min on the TFS to 35.5 min on ation period example for this unrestricted detour analysis is the DRFS. Te average computation time for this network presented in Appendix D. As before, increasing the was 459 seconds. Te gain on this network was smaller than 16 Journal of Advanced Transportation Table 9: Average passenger waiting, in-vehicle, and travel time for policy, and 53.5% with the unrestricted detour policy. 60 instances comparing limited detour policy and unrestricted However, the computation time increased from 56 to movements for the lines. 459 seconds to optimize one operation period. Tese results prove that a semifexible DRFS allowing limited detours can 2 stops detour Unrestricted Improvement provide a good solution in a faster time than a fully fexible p p p p p p p (%) tt tt tt wt vt wt vt DRFS. Despite somewhat long computation times, typical 30% empty for evolutionary algorithms that perform a random explo- 15.9 16.9 32.8 14.6 18.2 32.8 0.00 stops ration of the search space, these results also confrm the good 50% empty 15.7 16.6 32.4 13.7 18.1 31.7 2.20 performance of the MA. stops When evaluating the same instances with the DRFS 70% empty 14.7 16.4 31 12.8 17.3 30 3.30 obtained by the MA, and comparing it with the results of the stops same instances in the TFS, the average passenger waiting Average 15.4 16.6 32.1 13.7 17.9 31.5 1.70 time reduced with 31.4%, 48.1%, and 57.7% for the same network with two, three, and four lines, respectively. Despite slightly increasing the passengers’ in-vehicle time with 0.6%, Table 10: Average passenger waiting, in-vehicle, and travel times 0.6%, and 8.4%, respectively, the total travel time for the for TFS, and the solution of the MA for the DRFS considering the DRFS is always smaller than in the TFS. Tis reduction varies large network. between 6% and 73%. Another characteristic of of-peak operations, which are TFS solution MA solution Improvement the focus of this DRFS, is that there are a lot of empty bus p p p p p p p (%) wt vt tt wt vt tt tt stops along the routes. Tis feature is explored in these 30% empty experiments by categorizing the instances according to the 59.5 41 100.5 47.8 37 84.8 15.6 stops percentage of empty stops during the operation horizon. 50% empty 60.4 41 101.4 47.9 36.2 84.2 17.0 Increasing the percentage of empty stops in an instance, stops from 30% over 50% to 70% increased the benefts of the 70% empty 60.4 41 101.3 45.8 33.2 79.1 22.0 DRFS. For the same network, the average passenger travel stops time reduced with 28.2%, 29.6%, and 34.0% for these Average 60.1 41 101.1 47.2 35.5 82.7 18.2 clusters, respectively. In the network with 70 bus stops and three lines, the average passenger travel time reduced with 15.6%, 17.0%, and 22.0%, respectively. Tese results confrm the previous network, where lines could better “assist” other the efciency of the DRFS in low-demand of-peak opera- lines by taking over bus stops. In this larger network, stop tions. Te overall gains, however, are dependent on the skipping is not always used due to the unavailability of other network confguration and the line characteristics, as well as lines to take passengers from the skipped stops. Still, sig- the potential for shortcuts. nifcant improvements of on average 18.2% were obtained. Te results presented in this paper demonstrated the benefts of operating a DRFS to substitute a TFS. As such, it could be used to improve efciency of transit system in 6. Conclusion and Future Research suburban areas. However, the presented DRFS could be Tis paper presents a semifexible demand-responsive feeder further improved. For instance, by allowing buses to arrive at the station or depart from the terminal outside the operation system (DRFS) as a substitute to a traditional feeder system in suburban area. Te semifexible DRFS runs a service period and by cancelling services without passengers, the similar to a traditional feeder system (TFS), but with ad- frst situation can also be observed in the results in Appendix justable routes and timetables according to passengers’ re- B, where requests arriving late in the period are served quests. Its objective is to optimize passenger travel time. during the following period only. Allowing buses to arrive at the hub station after the operation period has fnished could From the operators’ perspective, the proposed system allows to ofer a more fexible system to the passengers using the improve the operation and increase the responsiveness of the system. However, it also means these buses might not be same resources. It does require a reservation system where passengers can make requests. available on time for the next operation period. Tis future implementation, however, would change the characteristic In order to optimize the operations of the DRFS, a memetic algorithm (MA) is developed, merging an evolu- of the system from static to more dynamic, with a rolling tionary metaheuristic with local search operations. Te re- horizon operation period and the possibility to reoptimize sults of the MA were found to have a travel time of the system when new requests arrive and some services are 0.1 minute longer than the optimal solution. Moreover, the already in operation. Tis approach is considered as future results of the MA were the same as in the optimal solution research. for seven out of ten periods. Also, as mentioned in the results in Section 5.4, the bus routes are not optimized when the buses are not carrying When comparing the performance of the DRFS, opti- mized with the MA, to the TFS for a network composed of 25 passengers, which might lead to unnecessary detours. Terefore, an improvement could be to modify the objective bus stops and three lines, the DRFS reduced the average passenger waiting time by 48.8% with the limited detour function value to remove these needless detours. It means Journal of Advanced Transportation 17 areas,” Journal of Transport Geography, vol. 88, Article ID optimizing the operation from the passengers’ perspective 102859, 2020. and from the operator’s perspective, aiming to ofer an [7] F. Bruzzone, M. Scorrano, and S. Nocera, “Te combination of efcient operation in terms of vehicle kilometers as well. e-bike-sharing and demand-responsive transport systems in Another limitation of the current DRFS is that it considers rural areas: a case study of Velenje,” Research in Trans- only the trips towards the hub station. Transfer times for portation Business & Management, vol. 40, Article ID 100570, passengers at the hub station are not considered, assuming a high frequency service from this point. In practice, hub [8] R. Mounce, S. Wright, C. D. Emele, C. Zeng, and J. D. Nelson, stations concentrate several diferent line services, and “A tool to aid redesign of fexible transport services to increase transfer time coordination plays a crucial role to improve efciency in rural transport service provision,” Journal of passengers’ experience using public transport. Synchroniz- Intelligent Transportation Systems, vol. 22, no. 2, pp. 175–185, ing these services at the station, as covered by Barabino et al. [26], and considering the transfer time at the station, as well [9] C. Bellini, G. Dellepiane, and C. Quaglierini, “Te demand as implementing a bi-direction service could improve the responsive transport services: Italian approach,” WIT service ofered by the semifexible DRFS and increase the Transactions on Te Built Environment, vol. 64, WIT Press, success of such a system. Ashurst Lodge, Southampton SO40 7AA, UK, 2003. [10] M. Diana, L. Quadrifoglio, and C. Pronello, “A methodology for comparing distances traveled by performance-equivalent Data Availability fxed-route and demand responsive transit services,” Trans- All instances and detailed results are made available at portation Planning and Technology, vol. 32, no. 4, pp. 377–399, https://www.mech.kuleuven.be/en/cib/drbp/. 2009. [11] Z. N. Kashani, N. Ronald, and S. Winter, “Comparing demand responsive and conventional public transport in a low de- Conflicts of Interest mand context,” in Proceedings of the 2016 IEEE International Te authors declare that they have no conficts of interest. Conference on Pervasive Computing and Communication Workshops (PerCom Workshops), pp. 1–6, IEEE, Sydney, NSW, Australia, March 2016. Acknowledgments [12] C. Archetti, M. G. Speranza, and D. Weyland, “A simulation Tis project was supported by Internal Funds KU Leuven study of an on-demand transportation system,” International Transactions in Operational Research, vol. 25, no. 4, (Project no. C24M/19/055). pp. 1137–1161, 2018. [13] R. J. R. Gomes, Dynamic Vehicle Routing for Demand Re- Supplementary Materials sponsive Transportation Systems, Doctoral dissertation, Uni- versidade do Porto – Portugal, Porto, Portugal, 2012. Appendix A: a mathematical model of a (simplifed) [14] P. Vansteenwegen, L. Melis, D. Akta¸, s B. D. G. Montenegro, semifexible Demand-Responsive Feeder System. Appendix F. Sartori Vieira, and K. Sorensen, ¨ “A survey on demand- B: an example result for one instance and discussion. Ap- responsive public bus systems. Transportation Research Part pendix C: layout of the network used for the instances and C: emerging,” Transportation Research Part C: Emerging the traditional fxed lines. Appendix D: an example solution Technologies, vol. 137, Article ID 103573, 2022. of the MA with unrestricted routes. (Supplementary [15] Y. Zheng, W. Li, and F. Qiu, “A methodology for choosing Materials) between route deviation and point deviation policies for fexible transit services,” Journal of Advanced Transportation, References vol. 2018, Article ID 6292410, 12 pages, 2018. [16] B. D. Galarza Montenegro, K. Sorensen, ¨ and [1] J. L. Schofer, B. L. Nelson, R. Eash et al., TCRP Report 98: P. Vansteenwegen, “A large neighborhood search algorithm Resource Requirements for Demand-Responsive Trans- to optimize a demand-responsive feeder service,” Trans- portation Services, Transportation Research Board, Wash- portation Research Part C: Emerging Technologies, vol. 127, ington DC, 2003. Article ID 103102, 2021. [2] C. Mulley and J. D. Nelson, “Flexible transport services: a new [17] J. Zhang, D. Z. W. Wang, and M. Meng, “Analyzing cus- market opportunity for public transport,” Research in tomized bus service on a multimodal travel corridor: an Transportation Economics, vol. 25, no. 1, pp. 39–45, 2009. analytical modeling approach,” Journal of Transportation [3] S. C. Ho, W. Y. Szeto, Y. H. Kuo, J. M. Leung, M. Petering, and Engineering, Part A: Systems, vol. 143, no. 11, Article ID T. W. Tou, “A survey of dial-a-ride problems: literature review 04017057, 2017. and recent developments,” Transportation Research Part B: [18] Y. Lyu, C. Y. Chow, V. C. Lee, J. K. Ng, Y. Li, and J. Zeng, “CB- Methodological, vol. 111, pp. 395–421, 2018. Planner: a bus line planning framework for customized bus [4] C. Iliopoulou and K. Kepaptsoglou, “Combining ITS and systems,” Transportation Research Part C: Emerging Tech- optimization in public transportation planning: state of the art nologies, vol. 101, pp. 233–253, 2019. and future research paths,” European Transport Research [19] R. Guo, W. Guan, W. Zhang, F. Meng, and Z. Zhang, Review, vol. 11, no. 1, pp. 27–16, 2019. “Customized bus routing problem with time window re- [5] A. Verma and S. L. Dhingra, “Developing integrated schedules strictions: model and case study,” Transportmetrica: Trans- for urban rail and feeder bus operation,” Journal of Urban Planning and Development, vol. 132, no. 3, pp. 138–146, 2006. portation Science, vol. 15, no. 2, pp. 1804–1824, 2019. [20] X. Li and L. Quadrifoglio, “Feeder transit services: choosing [6] M. Borjesson, ¨ C. M. Fung, and S. Proost, “How rural is too rural for transit? Optimal transit subsidies and supply in rural between fxed and demand responsive policy,” Transportation 18 Journal of Advanced Transportation Research Part C: Emerging Technologies, vol. 18, no. 5, pp. 770–780, 2010. [21] H. Yang, Z. Zhang, X. Liang, M. M. Abid, W. Fan, and L. Pu, “Optimal service design of demand responsive connector with elastic demand,” in Proceedings of the 2019 5th International Conference on Transportation Information And Safety (ICTIS), pp. 945–950, IEEE, Liverpool, UK, July 2019. [22] S. M. Nourbakhsh and Y. Ouyang, “A structured fexible transit system for low demand areas,” Transportation Research Part B: Methodological, vol. 46, no. 1, pp. 204–216, 2012. [23] K. Uchimura, H. Takahashi, and T. Saitoh, “Demand re- sponsive services in hierarchical public transportation sys- tem,” IEEE Transactions on Vehicular Technology, vol. 51, no. 4, pp. 760–766, 2002. [24] A. Pratelli, M. Lupi, A. Farina, and C. Pratelli, “Comparing route deviation bus operation with respect to dial-a-ride service for a low-demand residential area,” Data analytics, vol. 45, p. 151, 2018. [25] E. Vermeir, W. Engelen, J. Philips, and P. Vansteenwegen, “An exact solution approach for the bus line planning problem with integrated passenger routing,” Journal of Ad- vanced Transportation, vol. 2021, pp. 1–18, Article ID 6684795, [26] B. Barabino, M. D. Francesco, G. Maternini, and S. Mozzoni, “An ofine framework for the diagnosis of transfer reliability using automatic vehicle location data,” IEEE Intelligent Transportation Systems Magazine, vol. 14, no. 4, pp. 163–182, http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Advanced Transportation Hindawi Publishing Corporation

Optimization of a Semiflexible Demand-Responsive Feeder System in Suburban Areas Using a Memetic Algorithm

Download PDF
18 pages

Loading next page...
 
/lp/hindawi-publishing-corporation/optimization-of-a-semiflexible-demand-responsive-feeder-system-in-XNwrRG3peA

References (32)

Publisher
Hindawi Publishing Corporation
ISSN
0197-6729
eISSN
2042-3195
DOI
10.1155/2023/7593649
Publisher site
See Article on Publisher Site

Abstract

Hindawi Journal of Advanced Transportation Volume 2023, Article ID 7593649, 18 pages https://doi.org/10.1155/2023/7593649 Research Article Optimization of a Semiflexible Demand-Responsive Feeder System in Suburban Areas Using a Memetic Algorithm 1 2 1 Fabio Sartori Vieira , Kenneth Sorensen , and Pieter Vansteenwegen KU Leuven, KU Leuven Institute for Mobility CIB, Leuven, Belgium ANT/OR University of Antwerp Operations Research Group, Antwerp, Belgium Correspondence should be addressed to Fabio Sartori Vieira; fabio.vieira@kuleuven.be Received 6 September 2022; Revised 6 January 2023; Accepted 18 January 2023; Published 15 February 2023 Academic Editor: Zhihong Yao Copyright © 2023 Fabio Sartori Vieira et al. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Traditional bus operations in suburban areas are inefcient due to their fxed routes and timetables. Since suburban operations deal with low demand spread in a large area, the service stays underused for most of-peak hours. In order to render the operation proftable and increase the number of passengers on each bus, operators reduce the frequency of the service, which results in an increase of passenger waiting time for the service. As a solution to this problem, this paper introduces a demand- responsive public bus system that aims to adjust routes and timetables of a semifexible system to the demand for trans- portation. Te operation still ofers a reliable service like the traditional system but aims to reduce the passenger travel time. A memetic algorithm is developed to optimize this demand-responsive system. For a network with 25 bus stops served hourly by three lines and with an average demand of 20 requests per hour, the memetic algorithm is demonstrated to reduce the passenger waiting time with almost 50% in comparison with a traditional system operating in the same network with fxed routes and timetable. hours, feeder lines with fxed routes and timetables are no 1. Introduction longer efcient. Teir service is typically optimized for the Te growth of (sub)urban areas around big cities, such as demand predicted based on historical data, without con- new neighborhoods or settlements that operate as com- sidering external factors that might infuence the daily de- muting towns, puts pressure on public transportation mand using the service, such as weather conditions or systems. Tese new urban areas generally have a low nonregular events. population density spread over a large area. Direct con- Another approach to address this type of demand are nections or extensions of the current routes of the public fully fexible demand-responsive (taxi) services, which transport system potentially lead to a nonproftable service. operate without using fxed routes or timetables but pick up In order to improve the public transportation system in and drop of passengers according to their needs in a service complimentary to the traditional transit system, typically in these areas, the most applied solution is the implementa- tion of feeder lines. Feeder lines zigzag through the sub- a door-to-door service. In the OR literature, such systems are urban area to bring passengers to a hub station where a often modeled as a variant of the Dial-a-Ride Problem high-frequency service ofers a direct and fast connection to (DARP). Despite being a very responsive service, the op- the demand centers (city center, industrial zones, and eration of such systems in suburban areas with low demand schools). can also lead to low seat occupancy, and consequently, an Feeder lines partially solve the efciency problem in expensive operation. suburban areas with low demand, especially during peak Tis paper aims to investigate the applicability of a hours. However, when demand is lower during of-peak semifexible demand-responsive transportation system 2 Journal of Advanced Transportation experiments are performed for these instances. One last replacing a traditional feeder system in suburban areas. Te fact that this system is semifexible is a key novelty. experiment considers a large network and instances with more requests. Section 6 concludes the paper and dis- Tis means, on the one hand, it has some characteristics of traditional systems, i.e., a regular frequency of operation, cusses opportunities for further research. predefned standard routes, and a stop-based service. Tis “backbone” makes this system recognizable for the users 2. Literature Review and lowers the threshold for using it. Tus, this system still serves the demand by relying on the structure of the Tis section frst discusses the uprise of demand-responsive traditional feeder system. On the other hand, it is a de- systems, with diferent levels of fexibility. Ten, the DRFS is mand-responsive system, allowing modifcations to the positioned in the state of the art and various closely related standard routes and adjusting the timetable of each trip systems are discussed. while respecting the initial frequency. Terefore, our As an alternative for traditional systems, demand- proposed system falls in the category of a semifexible responsive systems emerged in the last decades and their demand-responsive feeder systems (DRFS) and intends to popularity has been rising over the years. One of the ofer an optimized service with some level of respon- initial, yet still popular, demand-responsive systems is a siveness to the actual demand for transportation yet still door-to-door dial-a-ride (DAR) system with the purpose based on a service running regularly. It should also be of transporting reduced-mobility or elderly passengers, noted that the same resources are being used as in the typically running in parallel to a fxed service [1]. Such a traditional system, so the operator costs remain the same system is also used as a transportation mode for rural and the focus will be on ofering a better service, with communities without scheduled bus services. Tis fully roughly the same operational costs. fexible system is typically operated based on reservations. As the traditional system, our semifexible DRFS is stop- After the surge of more innovative solutions and intel- based. It means that passengers willing to submit a request ligent transportation systems (ITS), more demand-re- must indicate beforehand their origin bus stop and walk to sponsive transport systems were developed for a wider the stop at the preferred departure time. Requests for a trip variety of purposes, complementing the fxed trans- can be submitted until just before the operation starts. Based portation systems [2–5]. on a list with all passenger requests, the routes and departure Several papers explore case studies to improve the times for the buses operating each line are optimized for current transit operation systems in rural areas (i.e., see [6]), each hour of operation of the services. Te objective when the implementation of alternative DRT systems and other optimizing the operations of this DRFS is to minimize the modes of operation (i.e., see [7]), or the optimal redesign of sum of the travel times for all passengers, from the moment the DRT systems to increase efciency [8]. Te common they arrive at the bus stop until they arrive at the hub station. characteristic identifed in transit operation in suburban or Terefore, a memetic algorithm (MA) is introduced to rural areas is the necessity of subsidies to make the service optimize the performance of the DRFS from the users’ viable. Terefore, it should be noted that our semifexible perspective. DRFS uses roughly the same resources as the traditional Te main contributions of this paper are that we in- feeder systems. troduce and analyze a new, semifexible, demand-responsive Depending on the transportation system proposed, feeder system, designed for low demand suburban areas. diferent levels of fexibility are considered that may afect Diferent from the other DRT systems, our semifexible stops, routes, timetables, or prebooking requirements [9]. system tries to combine the benefts of a fxed system and a On the most limited fexibility level, systems have been fully fexible DRT. Furthermore, a memetic algorithm is proposed with fxed bus stops, routes, and timetables, but designed for optimizing the performance of this new system which run only when a booking is made. On the other end of when serving a set of registered requests. After evaluating the the spectrum, a fully fexible system operates without pre- performance of the algorithm, the performance of the determined bus stops, routes, or timetables, serving users in system is analyzed and compared to the performance of a a service resembling that of a taxi. Tese fully fexible systems traditional feeder system. Tis allows determining under typically run using smaller vehicles, and routes are created which circumstances this new system should be considered according to passengers’ requests in a ridesharing format, in practice. with fxed or variable fares according to the travelled dis- Te related literature on public bus transportation tance and service availability. Some papers compare these systems is discussed in the next section, both for feeder fully fexible systems with other systems or traditional bus systems in general and for the DRFS. Te assumptions for systems using simulations [10–12]. Other papers focus on the DRFS proposed in this paper are described in Section developing guidelines for the operation and classifcation of 3. Te memetic algorithm is discussed in detail in Section these systems [13]. 4. Section 5 presents the results of the experiments. First, According to a recent and comprehensive survey and the efciency of the memetic algorithm is evaluated by classifcation of demand-responsive public bus systems [14], comparing its results with an optimal solution obtained our DRFS corresponds to a many-to-one, semifexible, stop- through a mathematical model. Ten, the DRFS is com- based, static demand responsive bus system. Tis means it is pared to the TFS. Several instances are generated, varying feeder line (“many-to-one”), with fxed stops (“stop-based”, the list of requests in each instance. Five diferent not “door-to-door”), but fexible routes and timetables Journal of Advanced Transportation 3 (“semi-fexible”), which are designed before the operation 3. Problem Statement starts (“static”). Moreover, with the objective of minimizing Tis section discusses the assumptions on the semifexible the passenger travel time, it takes the passengers’ perspec- demand-responsive feeder system (DRFS) and the required tive. Only a few of these systems have been considered before input data. Te starting point is a traditional feeder system [15, 16], but they consider systems with a completely dif- (TFS) operating a fxed number of bus lines with standard ferent design. routes and a regular timetable in a suburban area. Tis Still, other semifexible feeder services, combining system is optimized for the average daily demand. characteristics of both the traditional and demand-re- Te DRFS is designed to replace the TFS during of-peak sponsive systems, can be found in the literature. For ex- hours and will modify the standard route for each bus line ample, a customized bus (CB) ofers a regular operation towards the hub station and the departure time of the optimized to passengers’ requests, determining routes scheduled buses based on passenger requests. For every according to the pick-up and drop-of locations of pas- operation period of the problem, a list of passenger requests sengers. Te operation is adjusted on a daily basis, based on is available. Each request represents a trip by a passenger, the clustering of demand in the service area [17–19]. A with a desired bus stop and preferred departure time to start demand-responsive connector (DRC) operates a fully fex- the trip. Te standard route of each bus line can be modifed ible door-to-hub service in cycles [20]. However, the cost of with one or more shortcuts and limited detours. With such taxi-like or shuttle transit mode requires large cities “limited detours,” we mean that in each detour at most two with dense populations for a proftable operation [21]. additional stops can be visited before returning back to the Te resulting system from merging a demand-responsive standard route. Tis assumption guarantees, on the one and a traditional system can generate a substitute for the hand, that lines are still similar to the standard lines, and on traditional system or a complementary system running in the other hand, that sufcient opportunities are available for parallel. Nourbakhsh and Ouyang [22] explore a fexible shortcuts to skip bus stops without passengers and making service for low-demand areas, ofering a door-to-door ser- detours when appropriate. For the purpose of limiting the vice that substitutes the traditional operation. Tis system, fexibility in this study, the value was set to at most two however, is applied only for a grid network. In another additional stops per detour, creating a balance between a complementary system for high-demand areas with a grid fully fexible DRFS and the TFS with fxed lines. Tis value, structure, Uchimura et al. [23] design a hierarchical struc- however, could be infuenced by several other factors in ture. On the upper level, traditional mass transit lines reality, such as the availability of an alternative route be- connect diferent areas with an express service. Te inter- tween stops, or the ability to visit multiple diferent stops mediate layer operates an intercommunity traditional transit with only a small detour. Tis results in a limited pool of system ofering hub stations where passengers can switch to possible routes for each bus line. the last layer, which is the intracommunity service designed Figure 1 presents an example of the DRFS operation. As as a fully fexible door-to-door demand-responsive system. in the traditional system, a bus line is indicated by a unique Only a few of these systems could be used as a replacement nomenclature (a number, a code, or a color, for instance) system in low demand areas. and this nomenclature is used by passengers to identify the Another aspect taken in account for semifexible services bus line they need to their destination. In Figure 1, the is the way to structure the routes for the buses. Pratelli et al. standard line of the TFS is indicated as a solid line, with bus [24] design a demand-responsive feeder system were part of stops 6, 5, 4, 1, and the last stop S. In the DRFS, it can be the stops are fxed, as in the traditional system, but the decided, before the operation starts, to include the dashed demand-responsive operation allows deviations to include a detour, picking up passengers at stops 3 and 2 and skipping limited number of extra requests from optional stops. A stops 5 and 4. Tis result in two possible routes for this line: methodology to choose the most suitable policy is defned the standard line and the line with the dashed detour. according to the level of demand and the accommodation rate [15]. In our semifexible DRFS, the structure of the lines from the traditional feeder system are kept, such as a fxed 3.1.AssumptionsfortheDRFS. Te DRFS runs in a suburban terminal to begin the service and a common destination for area represented by a graph G � {V, E}, where V is the set of all requests. Limited fexibility from this original line allows bus stops (i � 0, 1, . . . , n), and i � 0 representing the hub optimizing the operation in of-peak hours considering the station. Edges E indicate links between bus stops i ∈ V and preferred departure time of the passengers. j ∈ V at a travel cost of c . Some initial assumptions for the i,j To conclude, our DRFS operates in suburban areas as a operation are as follows: many-to-one, semifexible, stop-based, static demand re- sponsive bus system, in order to substitute a traditional (i) Te objective of the DRFS is to minimize the total system in of-peak hours. Terefore, it keeps the traditional travel time of the passengers; feeder systems’ structure but includes fexibility in order to (ii) Te service operates for n consecutive periods; allow passengers to request a trip to the hub station at their (iii) Tere are a fxed number of lines connecting all the preferred departure time. Mainly, the aspects that it is a bus stops to the hub station; semifexible system and that it operates in of-peak hours making it diferent compared to other systems in the state of (iv) All lines start at a predefned terminal bus stop and the art. head to the hub station; 4 Journal of Advanced Transportation equation is the diference between drop-of at the hub station and the preferred departure time: p � p + p � p − p + p − p � p − p . (1) 􏼐 􏼑 􏼐 􏼑 tt wt vt p r d p d r In order to determine the penalty for a rejected request, it is assumed that passengers will be waiting for a bus until the next operation period. Since the routes for the next period are not defned yet, and since all buses depart from the terminal and arrive at the station within the operation period, it means that, in the worst case, rejected requests will arrive at the station by the end of the following operation period. Terefore, a passenger penalization (p ) is given by pen the time diference between the passengers’ preferred de- parture time and the end of the following operation period given by the following equation: p � 􏼐p − p 􏼑 + p � 2 ∗ p − p . (2) pen op r op op r Figure 1: Example of a line with two routes for the DRFS. 3.2. Generation of the Pool of Routes for the Lines. Te (v) Each bus is associated with a line, following a problem formulation of the DRFS uses a limited pool of route from the pool of routes generated for that alternative routes for each bus. In this subsection, we de- line; velop a method to generate such a pool. Te proposed (vi) Te pool of routes includes all feasible routes for semifexible DRFS focuses on operating a fexible service but each line, considering stop skipping and limited keeping the main characteristics of the TFS. Terefore, we detours; start from the standard (TFS) route of each line and then (vii) Te route length is limited to the duration of the generate a set of alternative routes using “stop skipping” and operation period (p ); op “limited detours.” (viii) Te buses depart from the terminal and arrive at Te standard routes are optimally designed for the TFS, the hub station within the operation period; serving all bus stops and efciently accommodating all the demand over multiple periods. In the DRFS, buses do not (ix) Te departure times of the buses are not fxed but follow these standard routes, but decide for the best route can be adjusted within the operation period; according to the requests for each operation period. Stop (x) Te bus capacity is assumed to be sufcient to skipping and limited detours are considered. Stop skipping address all requests. means that it is possible to skip one or a sequence of bus For each period of operation, there is a list of requests stops in the standard route. Detours mean that it is possible to include additional bus stops in the standard route. Since representing passengers that want to use the service during that period. Each request is composed of an origin bus stop the DRFS is not a fully fexible system where buses are and a preferred departure time (p allowed to take any possible route, we limit the detours to ) representing the mo- ment a passenger will be ready to take the bus towards the including at most two other bus stops before returning to a hub station. A request can be accepted or rejected. If ac- bus stop in the standard line. However, it is possible to cepted, it means that this passenger will be picked up by one combine detours with stop skipping. Furthermore, cycles are of the buses in that operation period at pick-up time (p ) not allowed, which means that a bus stop cannot be visited and will reach the station at drop-of time (p ). If a request is twice by the same bus. Moreover, a limit is set on the rejected, it means no bus will pass by the passenger’s bus stop maximum route length to control the maximum travel time after its preferred departure time, and a penalty will be a bus can ride. It should be noted that overlaps between associated with this request. Rejected requests are then in- diferent lines are possible, resulting in more than one line serving the same bus stop. cluded in the request list for the following operation period. After the last optimized of-peak period, it is assumed that By considering the limited detours, it is possible to precalculate all possible routes for each line in the DRFS. again the TFS is operated, serving all stops. Terefore, all passengers will be served. Tese alternative routes are then stored in a pool of routes Te main objective of the DRFS is to minimize the that are used by the memetic algorithm instead of recal- passenger total travel time (p ) by selecting, in each period, culating all possible movements while exploring solutions tt the best route and best departure time for each bus. Te total for the routes. As an example, Figures 2 and 3 illustrate a TFS travel time consists of the passenger waiting time (p ) at the operation in a grid network composed of nine bus stops and wt bus stop and the passenger in-vehicle time (p ) until a station S, served by a red line (Figure 2) and a blue line vt passengers arrive at the hub station. Terefore, the total (Figure 3). Figures 2 and 3 also indicate the possible detours travel time for each passenger given in the following or stop skipping for these lines, based on the previously Journal of Advanced Transportation 5 stated assumptions. For instance, the original route of the blue line includes the sequence of stops 9-8-7-4-1-0. When 3 6 9 the bus arrive at the stop number 8, it is possible to include a detour to stop number 5 instead of continuing the initial route to stop 7. From this point, the bus can return to the 2 5 8 original line, visiting stop number 4 and skipping the bus stop number 7, or include another detour to visit stop number 2. After this second detour, the bus is obliged to return to the original line. Te stop 3 cannot be included in 1 4 7 the blue route since it would require a detour of more than 100 two stops to return to the standard route. Tat is, from stop 9, it would require a detour to stop number 6 and then to stop number 3, but then it would require at least one more stop to return to the original line, which is not allowed. 0 100 200 300 Figure 2: Red line for a TFS operating a grid network and allowed 3.3. List of Requests and Operation Period. Every passenger detours and stop skipping. that wishes to use the system submits a request composed of a bus stop and a preferred departure time. It means pas- sengers are planning to arrive at the given bus stop and will be waiting for the bus from that moment on. Since the of- peak operation is divided in periods of operation, requests 36 9 have to be submitted before the start of the corresponding operation period. Once the buses of an operation period start running, no new requests for that operation period are 2 5 8 allowed. Terefore, the requests considered for the opti- mization of an operation period are those related to that operation period and unserved requests from previous operation periods. 1 4 7 4. Memetic Algorithm Approach Optimizing the performance of the DRFS discussed in the previous section is addressed with a memetic algorithm 0 100 200 300 (MA), combining an evolutionary heuristic suitable for Figure 3: Blue line for a TFS operating a grid network and allowed exploring large areas of the search space in coordination detours and stop skipping. with repair and improvement functions, acting as local search techniques, to improve solutions to ft the preferred period begins and takes a shortcut straight to bus stop 2, departure time of passengers. Te framework of the pro- posed MA uses diferent iterations to confgure the buses’ where the standard route is followed until the station. operation, i.e., route assignment and departure time for each bus. An overview of the MA is presented in Algorithm 1. 4.1. Population Generation. Te MA approach aims to Figure 4 illustrates the fowchart of the MA. For each identify, for each operation period, the solution that min- period of operation, the requests received for that period, the imizes the total passenger travel time. Te frst step of the rejected requests from previous periods and the list of MA is to populate the initial generation with solutions. Since possible routes for each line are considered as input. Sub- all buses must arrive at the station before the end of the sequently, a generation with initial solutions is created and operation period, the route length determines the maximum the ftness value for each solution is calculated. Ten, the delay time a bus can have. Terefore, the route is assigned process of selection, crossover, mutation, repair, and im- frst; selecting a random route from the pool of routes for provement is repeated until a given number of generations is each line, and then, a departure time is assigned randomly produced without further improvement of the best solution. limited to the maximum delay time. Tis random generation For each operation period in the operation horizon, a tries to cover a large number of possible combinations of solution is represented by a list of bus stops and a departure routes and departure times as possible, which are then time from the terminal for each bus line of the service. Te subjected to further improvements in the following route is represented by a sequence of bus stops and the generations. departure time with a delay from the beginning of the operation period. For instance, a possible representation for the red line service on Figure 2 could be the route that 4.2. Evaluation of Solutions. After assigning a route and a departs from the terminal 20 minutes after the operation departure time to each line of the operation period, it is 6 Journal of Advanced Transportation Start: For each line in set of line: Initialize pool of possible routes for line Append requests of the current operation period in the list of requests Append rejected requests from previous periods in the list of requests Generate n initial solutions Identify the list of 5% best solutions Repeat: Create a new empty generation Add the 5% best solutions from previous generation Repeat: Generate two new solutions with crossover operation Apply mutation on these two solutions Evaluate solutions Until solutions in the new generation � n Apply repair operation to all solutions Apply improvement operation to all solutions Update list of 5% best solutions Until termination criteria ALGORITHM 1: MA full algorithm pseudo-code. possible to generate the timetable for all bus stops and the Start arrival time of the buses at the station. Tis information is used to evaluate the objective function value of the solution using the list of requests for the current operation period. List of requests Te ftness of a solution is given by the sum of passenger travel time for all requests in the list of requests (r ∈ R) as Pool of follows: routes Objective function value � 􏽘 p + p . tt pen (3) r∈R Initialization For every request in the list of requests, the passengers’ preferred departure time (p ) is compared with the time- table for that bus stop. If a passenger arrives at the bus stop Fitness calculation before the bus, the request is accepted and p and p are p d updated. If the passenger arrives at the bus stop after the bus passed by, or no bus visits the stop in that operation period, the request is penalized, and this request is included in the Yes Termination list of requests for the next operation period. If more than criteria one bus from diferent lines can serve a passenger in the same operation period, the one that arrives earlier at the No station is chosen. It should be noted that this is not nec- essarily the frst bus serving the stop. Selection After evaluating the new solutions in a generation, they are sorted according to the ftness value, and the solution with the smallest ftness is set as the best solution of the generation. Also, the top 5% of the solutions are set as good Crossover/Mutation solutions for the elitist crossover method (below). If the population size is smaller than 100 solutions, at least fve solutions are set as good solutions. Te evaluation ftness function is presented in Algorithm 2. Repair/Improvement 4.3. Crossover Operation. Te frst operation to populate new generations is the crossover. Te MA uses two diferent End methods: an elitist and a random crossover, with a proba- Figure 4: Flowchart of the memetic algorithm. bility of 50% each. In the elitist method, at least one of the Journal of Advanced Transportation 7 Start: Solution ftness � 0 For request in list of requests: If preferred departure time at request stop≤ bus arrival at request stop: p � time bus arrive at bus stop p � time bus arrive at station p � p − p tt d r Solution ftness + � p tt Else: p � 2 ∗ p − p pen op r Solution ftness + � p pen Return Solution ftness ALGORITHM 2: Fitness evaluation. parents is selected from the group of good solutions. Te to be served on one of the lines. If the request is rejected due other parent is randomly selected. In the random crossover, to early service, the repair function tries to delay the cor- both parents are selected randomly from the general pop- responding bus as much as possible, so the bus arrives at the ulation. Once the parents are selected, the crossover selects bus stop at the same time as the passenger. It consequently the routes of the lines and the departure time from the delays all arrival times for all the bus stops in the route and parents to generate two new solutions. It is done by ran- thus increases the waiting times for other passengers. Ob- domly assigning to each line of one new solution, the route viously, this delay is limited by the fact that the bus should and departure time used by a randomly selected parent on arrive at the hub station before the end of the operation period. this line. Te nonselected route (and departure time) for that line is then assigned to the second new solution. Te A more complex procedure is executed if the request is crossover operation is presented in Algorithm 3. rejected due to an unserved bus stop. First, one of the possible lines that may serve the bus stop is selected. In the example of Figures 2 and 3, for instance, bus stop three can 4.4. Mutation Operation. Te mutation operation includes only be served by the red line, bus stop seven only by the blue variability in the generations by changing routes and de- line, and all the others bus stops by both lines. Second, parture times of a solution after the crossover method, with a considering the current route for the selected line, all bus 5% probability of occurring. A mutation can be a small or a stops where passengers are being served by this route are large mutation, each with a 50% probability. In the small marked, and a new route including all these marked bus mutation, one route and departure time of the solution is stops and the bus stop of the rejected request is chosen from randomly modifed. In the large mutation, all routes and the pool of routes for this line. Finally, the procedure checks departure times are generated again for that solution, whether the departure time needs to be adjusted, either resulting in a completely new solution. Tese new solutions because the new route is longer than the previous or because are introduced to stimulate diversifcation in the population. the arrival time at the included bus stop is still not serving After the mutation operation, the new solution is included in the penalized request. the new generation list, whether mutated or not. Te mu- An example of this procedure is illustrated in Figure 5. In tation operation is presented in Algorithm 4. this example, there is a penalized request at bus stop four, not served by neither the red line (a) nor the blue line (b), 4.5. Repair Operation. After populating the new generation, since this bus stop can be included in both the lines, stops with served passengers on the current route of the lines are all solutions pass through both the repair and the im- provement operations. Te repair operation modifes the marked: stops 8 and 1, if the red line is chosen, and stops 8 and 2 for the blue line. Tere are no possible routes including solution, trying to avoid penalized requests and accepting them in the current period. First, all rejected requests in the the stops 8, 4, and 1 in the same route for the red line, list of requests are categorized according to the type of therefore, this option is discarded. For the blue line, it is penalty, i.e., whether the penalty results from an early bus possible to change the route to the sequence illustrated on service or from an unserved bus stop. An early bus service Figure 5(c). Te last check adjusts the departure time for the means a passenger arrives at the requested bus stop after the optimized request. Te bus in the blue line departs at the last bus has already served that bus stop, and consequently, beginning of the operation period. It will serve bus stop 4, this passenger is not served. In the case of an unserved bus 15 minutes later with the new route. If the passenger arrives stop, the bus stop is not visited by any bus in the current any time earlier, there will be no adjustment in the departure time of the bus. If the passenger arrives later, the departure solution, and passengers requesting travel from these stops are forced to wait for the next period. time of the bus will be delayed as much as possible, so this passenger does not have to wait for the bus, respecting the Once all penalized requests are categorized, one of them is randomly selected to be “repaired” by forcing this request maximum arrival time at the station. 8 Journal of Advanced Transportation Start: Random selection of crossover method: elitist or random If elitist: Choose random parent (P ) from the list of best solutions If random: Choose random parent (P ) from previous generation Choose second random parent (P ) from previous generation Create empty ofspring -> O , O 1 2 For line in set of lines: Random selection order: true or false If true: O receives line confguration from P 1 1 O receives line confguration from P 2 2 If false: O receives line confguration from P 1 2 O receives line confguration from P 2 1 ReturnO , O 1 2 ALGORITHM 3: Crossover operation. Start: mutation probability � Random number between (0, 100) If mutation probability≤ 5: Choose mutation size: small or large If small: Choose a random line from solution Select a random route in the pool of routes for this line max departure time � operation period time–route length bus departure � random time between (0, max departure time) If large: For each line in set of lines: Select a random route in the pool of routes for this line max departure time � operation period time–route length bus departure � random time between (0, max departure time) Return Solution ALGORITHM 4: Mutation operation for new solutions. Departure: +18′ Departure: +0′ Departure: +0′ 8 2 8 2 8 14 4 4 (a) (b) (c) Figure 5: Example of a repair operation for a small grid network to include a request in bus stop 4 in the red or the blue line: (a) the current red line with passengers at stops 8 and 1; (b) the current blue line with passengers at stops 8 and 2; (c) fnal solution adapting the blue line. Journal of Advanced Transportation 9 After fnishing the repair operation, the new solution is created. In these instances, buses are allowed to take any re-evaluated, and if the ftness is improved compared to the route in the network from terminal to station. Finally, the previous one, the new repaired solution replaces the earlier MA is evaluated on larger instances, with 70 bus stops in the solution in the new generation. Otherwise, it is discarded. area instead of 25 bus stops. Tese two last experiments allow evaluating the viability of the MA to fnd local optima for complex instances and to check the performance of the 4.6. Improvement Operation. Te last operation included in DRFS. the MA is the improvement operation. While the repair operation tries to delay the departure time of buses or to 5.1. Network and Instances. Since this DRFS was not studied include stops not served in the routes, the improvement before, there are no benchmark instances available to operation advances the departure time of a bus or makes the evaluate the performance of the MA. Terefore, new in- route more direct to the destination. Te operation starts stances are created based on a graph corresponding to a with the selection of a random request from the list of suburban area served with a feeder bus system. It is com- accepted requests. After checking which bus is currently posed of 25 bus stops connected to a transfer station (S) and serving the request, two steps are executed. First, it tries to served by three lines. All lines start at bus stop/terminal 25. fnd a new route aiming to reduce the in-vehicle time for the Each bus stop expects 1 to 6 passengers, with a total of 100 passenger of this request. As in the previous operation, all requests over fve consecutive operation periods. Te time a bus stops serving passengers along the current route are bus takes from one bus stop to another is equivalent to the marked. Ten, a new route is selected for this line only when Euclidian distance between the bus stops, converted to there is a shorter route for the selected request with all the minutes, and presented in Figure 7. Te length for the marked bus stops along the route. Second, the bus departure standard lines for the TFS and the number of alternative is set earlier as much as possible to reduce the waiting time routes in the pool of routes for each line in the DRFS are for this request. Te new solution replaces the earlier one in presented in Table 1. Te lines for the TFS are optimized to the new generation if the improvement operation improves serve the total demand presented in Table 2. Tese lines are ftness. obtained with an exact optimization approach developed for Te operation of the improvement function is illustrated the bus line planning problem considering the average daily in Figure 6. In this example, there is a request for bus stop 2 demand expected at the diferent bus stops [25]. Te ob- with the preferred departure time 30 minutes after the pe- jective is to minimize the passenger travel time from the riod starts, and this passenger is served with a bus from the diferent bus stops to the hub station. It results in the optimal blue line following route illustrated on the left in Figure 6. standard routes for the lines of the TFS. In a second step, the Te current departure time from the terminal is 25 minutes frequency of the service is set to one bus per line per op- after the beginning of the period, and the bus is picking up eration period. Tis procedure is similar to the planning of the selected passenger at time 40. Terefore, the waiting time traditional feeder systems in practice. for this passenger is 10 minutes. In the improved solution, One instance with fve operation periods is shown in on the right in Figure 6, the route is kept unchanged since Table 3. In each operation period of this example, requests there is no route in the pool of routes with a shorter in- are concentrated in 9 to 15 diferent bus stops of the 25, vehicle time from bus stop 2 to the station. Ten, the bus is corresponding to, on average, half of the bus stops per set to depart 10 minutes earlier, consequently arriving earlier operation period. Tis means that in the total operation at every bus stop along the way and picking up the passenger horizon, there are 50% of stops without requests (50% of at bus stop 2 without any waiting time. If other passengers empty bus stops). Several instances with random distribu- are being served by this bus, there are two options: their tions of demand were created, categorized according to the waiting times are reduced by 10 minutes, or their requests number of empty bus stops in the total operation: 30%, 50%, are rejected in this solution. After updating the route and the or 70%. timetable, the new solution is re-evaluated, and if the ftness is better, the new solution replaces the earlier one in the new generation. Otherwise, it is discarded. 5.2. Sensitivity Analyses forMA’s Parameters. Tis sensitivity analysis examines the parameters for the MA, i.e., the size of the population in each generation and the stop criteria in the 5. Results search for improvements. In order to somewhat limit the In this section, results for the MA are presented in six computation time required to optimize an operation period, population sizes of 50, 100, or 200 are considered combined analyses: First, benchmark instances for the DRFS are created and the parameters of the MA are evaluated in a with a maximum number of generations without im- sensitivity analysis. Te MA is then validated through a provements of 20, 50, or 100. Beyond these parameters, the comparison with a mathematical model that solves a very total number of generations was limited to 1.000. During the similar but somewhat easier problem to optimality. Second, experiments reported in this paper, however, this value was the MA solutions for the benchmark instances are compared never reached. with those of a TFS. Tird, instances are generated with Te results for this sensitivity analysis are presented in Table 4 for 15 instances grouped in three categories variations in the number of lines. Fourth, more complex instances without restriction on the possible detours are according to the percentage of empty stops (30%, 50%, and 10 Journal of Advanced Transportation Stop 2, Dep. time: +40’ Stop 2, Dep. time: +30’ Request for stop 2 Request for stop 2 p = 10ʹ p = 0ʹ w at time: + 30’ at time: + 30’ Figure 6: Illustration of improvement operation for a request and the improved line, advancing the departure time of the bus 10 minutes to reduce the waiting time of this passenger. Table 2: Expected demand for each bus stop during the entire 5 15 operation horizon. Stops Demands 1 1 2 4 4 9 3 6 4 1 5 4 6 4 7 2 8 6 9 6 10 4 11 1 12 6 13 6 14 2 15 6 16 4 17 6 18 6 S 100 200 300 400 500 19 4 20 6 Figure 7: Network representing a suburban area, served by three 21 4 lines in a TFS. 22 4 23 1 24 2 25 4 Table 1: Network characteristics: length of lines for the standard route in the TFS; number of routes in the pool of routes for each line in the operation period. considering the quality of the results, we conclude that a Lines Route lengths (min) Pool of routes size population size of 100 solutions and a stop criteria of 50 generations without improvements are appropriate param- Red 32.1 192 Green 33.2 60 eter values, increasing the population size from 100 to 200 or Blue 28.2 225 the maximum number of generations without improvement Combinations of routes: 2.592.000 from 50 to 100 produced the same passenger travel time on average (31.8 min) for these 15 instances, but the computation Operation period duration: 60 min time increased from 55 to 126 and 132 seconds, respectively. Reducing these parameters increased the optimal value of the 70%), with fve instances for each group. Te results present solutions. We conclude that the selected parameters values the average passenger travel time in minutes, and the com- guarantee (at least for these instances) a reasonable number of putation time in seconds. Considering the limited available generations before reaching the stop criterion and sufcient time for computations just before each operation period, and diversity in the population. Stop 9, Dep. time: +25’ Stop 8, Dep. time: +30’ Stop 5, Dep. time: +35’ Stop 1, Dep. time: +45’ Station S, Dep. time: +55’ Stop 9, Dep. time: +15’ Stop 8, Dep. time: +20’ Stop 5, Dep. time: +25’ Stop 1, Dep. time: +35’ Station S, Dep. time: +45’ Journal of Advanced Transportation 11 Table 3: Example of demand distribution in the operation horizon, corresponding to fve operation periods. Bus stops Requests Stops w/o Empty per requests stops (%) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 period 1st 0 2 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 2 0 0 0 0 0 1 0 11 16 64.00 2nd 1 2 0 1 0 2 0 1 3 2 0 1 1 0 0 2 2 1 1 0 0 0 1 0 2 23 10 40.00 Op. 3rd 0 0 3 0 2 0 0 2 1 0 0 2 2 0 2 0 2 0 2 0 2 0 0 0 0 20 15 60.00 Period 4th 0 0 2 0 1 0 0 2 1 1 0 2 2 2 1 0 2 3 1 0 2 3 0 0 1 26 10 40.00 5th 0 0 1 0 1 1 1 1 0 1 1 0 0 0 3 1 0 0 0 6 0 1 0 1 1 20 12 48.00 Sum of 1 4 6 1 4 4 2 6 6 4 1 6 6 2 6 4 6 6 4 6 4 4 1 2 4 100 63 50.00 demand Table 4: Sensitivity analysis of the MA for a population of 50, 100, or 200 solutions and the stop condition without improvements of the best solution for 20, 50, and 100 iterations. Results show the passenger travel time (t.t.) and the computation time (CPU). Max. number of iterations without improvements 20 50 100 Population sizes t.t. (min) CPU (s) t.t. (min) CPU (s) t.t. (min) CPU (s) 30% 33.5 18 33.8 34 33.2 69 50% 31.7 16 31.7 38 31.1 64 70% 31.3 17 31.4 34 31.2 63 Avg 32.2 17 32.3 36 31.8 66 30% 33.7 29 33.4 60 33.1 128 50% 31.4 29 31.1 54 31.3 125 70% 31.1 29 30.9 52 31 143 Avg 32.1 29 31.8 55 31.8 132 30% 33.4 57 33.4 122 32.8 249 50% 31 58 31.3 118 30.8 193 70% 30.4 62 30.7 138 30.7 242 Avg 31.6 59 31.8 126 31.4 228 optimization for the DRFS. Te routes for the demand il- 5.3. Performance of the MA. Tis frst analysis evaluates the performance of the MA by comparing its solutions with the lustrated in Table 3 are shown in Figure 8 as an example for optimal solutions obtained with the exact model of a similar the three solutions (TFS and optimal solution and MA problem solved with CPLEX. In this model, buses depart at solution for the DRFS) on all fve operation periods. Buses the beginning of the operation period for all lines, and no depart at the beginning of the operation period for all lines in exact arrival times of passengers at the bus stops are con- the TFS and in the optimal solution for the DRFS, due to the sidered. Instead, all passengers are assumed to be present at initial assumptions. In the solution found by the MA for the the bus stop at the beginning of each operation period. DRFS, the departure times identifed by the algorithm were Terefore, in all instances considered in this subsection, all also equal to the beginning of the operation period for all preferred departure times are set equal to the beginning of lines. the operation period. Tis also implies that all passengers are For this analysis, data for twenty operation horizons were randomly generated for each percentage of empty served in the operation period for which they submitted a request, and the preferred departure time is always zero. Due stops, and with fve operation periods each. Terefore, 300 to this simplifcation, the model can be solved to optimality operation periods are optimized both with the mathematical for the size of instances considered. Te model is presented model in CPLEX and using the MA. Both waiting and in- and discussed in Appendix A (available here). vehicle times of passengers are evaluated, considering the For this analysis, data for twenty operation horizons standard routes for the TFS, and the optimal routes obtained were randomly generated for each percentage of empty by CPLEX, and the routes obtained with the MA optimi- stops, and with fve operation periods each. Terefore, 300 zation for the DRFS. Te routes for the demand illustrated in operation periods are optimized both with the mathematical Table 3 are shown in Figure 8 as an example for the three solutions (TFS and optimal solution and MA solution for the model in CPLEX and using the MA. Both waiting and in- vehicle times of passengers are evaluated, considering the DRFS) on all fve operation periods. Buses depart at the standard routes for the TFS, and the optimal routes obtained beginning of the operation period for all lines in the TFS and by CPLEX, and the routes obtained with the MA in the optimal solution for the DRFS, due to the initial 12 Journal of Advanced Transportation DRFS – Mathematical TFS DRFS – Memetic Algorithm model 500 500 500 400 400 300 300 200 200 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 200 100 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 200 100 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 200 100 100 100 0 0 0 500 500 500 400 400 400 300 300 300 200 200 100 100 0 0 0 200 400 0 200 400 0 200 400 st nd Figure 8: Routes for total operation in the TFS (1 column), the optimal solution obtained with the mathematical model for the DRFS (2 rd column), and the solution obtained for the DRFS with the MA (3 column) for all the fve operation periods of one instance. 5th Period 4th Period 3rd Period 2nd Period 1st Period 5th Period 4th Period 3rd Period 2nd Period 1st Period 5th Period 4th Period 3rd Period 2nd Period 1st Period Journal of Advanced Transportation 13 comparison with results obtained by solving the mathe- assumptions. In the solution found by the MA for the DRFS, the departure times identifed by the algorithm were also matical model. In this second part of the analysis, the de- mand distribution over the diferent stops is the same as equal to the beginning of the operation period for all lines. As mentioned before, routes are identical for all oper- before for the 60 instances, but the preferred departure time ation periods in the TFS. Six routes in the optimal DRFS can take any value within the operation period. Tis means solution are the same as in the TFS. It happens in the frst that some preferred departure times occur after the bus has three operation periods for the red line and in the frst, already served the respective bus stop, and these passengers second, and ffth period for the green line. Eleven out of are left to be served in the following operation period. Tis ffteen routes for the lines in the DRFS obtained with the MA results in a variation in the average passenger waiting time, even for the TFS. For the demand presented in Table 3, the are identical to the optimal DRFS solution. All routes ob- tained with the MA solution were identical to the optimal MA solution for the third operation period is illustrated in Figure 9, as an example. For this solution, the bus in the blue solution for the frst and ffth operation periods. Tere are slight variations in the routes obtained for the second and line departs two minutes after the operation period begins, at time 02 : 02, and arrives at the station at 02 : 35. Te bus in the fourth period. Te average passenger travel time for this instance is presented in Table 5 for each operation period. the green line departs at 02 :17, and arrives at the station at For the TFS, the average passenger travel time was 31.5 min. 02 : 55. Te red line bus departs at 02 :19, arriving at 02 : 53, For the DRFS, this value was 10.8% lower with the optimal 7 minutes before 03 : 00, the end of the period. Buses pick up solution, representing a reduction of 3.4 minutes. For the passengers in the bus stops marked in the fgure. Results for solution obtained with the MA, the average passenger travel this instance and routes for the fve operation periods in the time was 0.1 minutes longer than the optimal solution. MA solution are presented in Appendix B, together with the full table with the scheduled departure time for each pas- Te optimal travel time for passengers was achieved in four out of fve optimized periods with the MA. As men- senger for this operation period. tioned before, the MA found identical routes as in the optimal solution for the frst and the last operation periods, 5.4. Results of the MA for General Instances. Te results for so both simulations present the same results. For the second the MA are compared to the TFS for all the 60 instances, and the fourth operation periods, even though routes were grouped by the percentage of empty stops, and presented in not the same for all the lines as in the optimal solution, the Table 7. Tis table shows the average passenger waiting, in- obtained results with the MA were the same as the optimal vehicle, and total travel time for the TFS and the DRFS with result. It means that diferent routes serve passengers with the MA solution. On average, the time passengers spend on the same efciency as in the optimal solutions. Passengers in the bus in the optimal routes of the DRFS is slightly in- the third period had an average travel time of 29 minutes creased compared to the time passengers took while trav- with the solution of the MA, a value 2.5% above the optimal eling using standard routes in the TFS. However, this value solution. decreases the more empty stops are present in the instances. Tis same analysis was repeated for all 60 instances, It means that detours included in the lines’ routes to serve comparing the average passenger travel time for the TFS, passengers increase the average in-vehicle time, but skipping and the optimal and the MA solution for the DRFS (Table 6). empty bus stops can reduce it. On the other hand, the av- In the optimal solutions, the average passenger travel time erage passenger waiting time on the DRFS reduced by 48.1% was 8.6% shorter than the TFS solution, while the MA could compared to the TFS, with an overall improvement of 30.6% improve the passenger travel time by 8.0%. Moreover, the on passenger travel time. However, since the memetic al- results of the MA were the same as in the optimal solution in gorithm’s objective is to improve passenger travel times, the 69.3% of the operation periods. Increasing the percentage of routes taken by buses while not carrying passengers are not empty stops does not make any diference in passenger travel always the shortest route possible. Tis does not imply that time on TFS because routes for the lines are identical for the these solutions can be further improved, because bus driving whole operation period. In the optimal and the MA solutions time is not part of the objective function and the buses are for the DRFS, however, increasing the percentage of empty optimally serving passengers. Te average calculation time to bus stops in the instances allows the possibility to skip empty achieve the termination criteria for the MA was 56 seconds bus stops and serve busy bus stops faster. With 30% empty per operation period. stops, passenger travel time was 1.3 minutes shorter in the optimal solutions than in the TFS. With 70% of empty stops, this value was 4.5 minutes shorter. On average, passengers 5.5. Results of the MA for Varying Numbers of Lines. Te could arrive at the station 2.7 min earlier if the routes of the previous analyses consisted of a network with three lines. In TFS could be adapted and changed dynamically. Comparing this section, the same network with the same demand is now computation times for these simplifed instances, the served by a system with two and four lines instead of three, in order to analyze the impact of that parameter. To make a fair mathematical models took 6.5 seconds on average to identify the optimal solution for each period of operation, and the comparison with the TFS, the lines of the traditional feeder system are optimized using the MA, considering the total MA took 52 seconds on average. In the previous analysis, passengers requested their trips demand for entire operation horizon both for two and four to start exactly at the beginning of the operation period, in lines. Te standard lines for the TFS services for two and four order to generate a simplifed problem, allowing the lines are presented in Appendix C. 14 Journal of Advanced Transportation Table 5: Average p for each period of the example simulated. tt MA solution Periods TFS solution (min) Optimal solution (min) (min) 1st 31 28.3 28.3 2nd 30.9 29.4 29.4 3rd 31.8 28.3 29 4th 32.4 27.1 27.1 5th 31.3 27.4 27.4 Average 31.5 28.1 28.2 Table 6: Average passenger travel time in the TFS, with optimal routes and the MA. Improvement of optimal and MA solution compared to TFS, classifed according to the percentage of empty bus stops in the instance. TFS solution Optimal solution Optimal solution improvement MA solution MA solution improvement (min) (min) (%) (min) (%) 30% empty 31.5 30.2 4.2 30.5 3.2 stops 50% empty 31.5 29.1 7.6 29.3 7.1 stops 70% empty 31.5 27.0 14.1 27.2 13.7 stops Average 31.5 28.8 8.6 29.0 8.0 Departure:+19ʹ Departure:+17ʹ Departure:+2ʹ 0 100 200 300 400 500 0 100 200 300 400 500 0 100 200 300 400 500 Figure 9: Example of MA solution for the third operation period with 50% of empty stops. and four lines is that the area considered can be covered Table 7: Results of average passenger waiting, in-vehicle, and total easily with only three lines and therefore all three (or four) travel times for the TFS and the MA grouped by percentage of empty stops in the instances. lines have a length close to the minimal travel time between the terminal and the hub station. With only two lines, longer TFS solution MA solution Improvement lines are required to cover the area. Terefore passengers p p p p p p p (%) wt vt tt wt vt tt tt have to wait longer for their buses and spend more time 30% empty inside the vehicles before reaching the hub station. Tese 29.1 16.5 45.6 15.9 16.9 32.8 28.20 stops results are presented in the frst columns of Table 8. 50% empty When there are four buses in the semifexible DRFS, the 29.4 16.5 45.9 15.7 16.6 32.3 29.50 stops optimization adjusts better to the passengers’ expectations. 70% empty 30.5 16.5 47 14.7 16.4 31.1 34.00 On average, the passenger travel time in the DRFS is 37.6% stops shorter compared to the TFS, while this was 30.6% for three Average 29.7 16.5 46.2 15.4 16.6 32.1 30.60 lines and 29.8% for two lines on the DRFS. Te passenger waiting time reduced on average with 8.9, 14.3, and 16.8 minutes for two, three and four lines. On the other Te average lengths of the TFS lines with two, three, and hand, it is possible to identify a reduction in the in-vehicle four lines are 50.5, 31.2, and 29.3 minutes. Te reason why times of passengers for two lines only (7.9 minutes). For the average length of the lines are roughly the same for three three and four lines, the passenger in-vehicle times increased Journal of Advanced Transportation 15 Table 8: Average passenger waiting, in-vehicle, and travel time for 2 or 4 lines. TFS solution MA solution Improvement p p p p p p p (%) tt tt tt wt vt wt vt 30% empty stops 28.1 27.7 55.8 20.3 20.7 40.9 26.60 50% empty stops 28.4 27.7 56.1 20.2 19.8 40 28.60 2 lines 70% empty stops 28.8 27.7 56.5 18.1 19 37.1 34.30 Average 28.4 27.7 56.1 19.5 19.8 39.4 29.80 30% empty stops 29.1 16.5 45.6 15.9 16.9 32.8 28.20 50% empty stops 29.4 16.5 45.9 15.7 16.6 32.4 29.50 3 lines 70% empty stops 30.5 16.5 47 14.7 16.4 31 34.00 Average 29.7 16.5 46.2 15.4 16.6 32.1 30.60 30% empty stops 28.4 15.5 44 12.9 15.8 28.7 34.70 50% empty stops 29.1 15.5 44.7 12.1 15.7 27.9 37.60 4 lines 70% empty stops 29.8 15.5 45.3 11.7 15.3 27 40.40 Average 29.1 15.5 44.7 12.3 15.6 27.9 37.60 0.1 minutes. It means that more options for stop skipping to percentage of empty bus stops in the simulation reduced the shorten the routes are available with two lines. With three or in-vehicle time as well, and this gain is refected in the average passenger total travel time. From 32.1 min with four lines, detours optimize the passenger waiting time, but the average length of routes are roughly the same. limited detours, the average travel time obtained with the MA solution with unrestricted detours was reduced to Te average computation time per operation period was 53 seconds for the network with 4 lines, while in the network 31.5 min. Te average computation time for the optimiza- with two lines, the computation time was 93 seconds. Longer tions was 407 seconds. routes also mean a bigger search space for the MA, refected in the number of routes in the pool of alternative routes. 5.7. Large Network Instances. One last analysis considers a larger network with 70 bus stops and a centralized hub, and 5.6. Instances with Unrestricted Detours. So far, the possible 300 requests in fve operation periods. Te large network and the standard lines of the TFS are presented in Appendix detours that a bus could make were restricted to at most two bus stops from the original route. In this analysis, the same C. Here, again three lines are considered to serve the bus stops, with fxed terminal on bus stops 1, 63, and 70. In order instances are considered, but buses are allowed to take any possible route in the network. Tis will allow to further to identify the standard routes for the TFS, the MA was used analyze the performance of the MA and to evaluate the with the total demand for the entire operation horizon and opportunity of allowing more fexibility in the routes. Still, unrestricted detours for the lines were allowed. Tis pro- no cycles are allowed, and the route length is limited by the cedure does not guarantee the optimal routes for the lines as duration of the operation period. in the previous network but leads to a good solution given Te number of possible routes generated for the pool of the complexity of the network. Since routes are now much routes increases from 192 for the red line, 60 for the green, longer and the same numbers of buses are available, the and 225 for the blue line with at most two bus stops outside operation period considers a frequency of one bus every two hours. Terefore, for the DRFS, the routes were limited to the original route (Table 1), to 2,149 routes with unrestricted detours for each line. All possible combinations from the not exceed 120 minutes. All the other rules were kept as initially, considering the possibility of deviating from the terminal to the station are considered. Terefore, the search space increases from 2.6 million possible combinations to 10 standard route to include at most two extra bus stops or to billion. Beyond that, it is still necessary to identify the op- skip stops. Fifteen instances were optimized with this net- timal departure time for the buses considering preferred work, fve for each group according to the percentage of departure time for the requests. empty stops (30%, 50%, and 70%). As before, the variation Results for the same 60 instances as in the analysis in between instances occurs on the randomization of the Section 5.4 are presented in Table 9, comparing the solutions preferred departure time of passengers and the operation period on which the trip is requested. Results are presented obtained with the MA for the limited and unrestricted detours. Beyond the initial reduction in travel time observed in Table 10. Since the operation period is two hours and requests for the DRFS in comparison to the TFS, the value was further reduced by 1.7% with unrestricted detours. Te average arrive randomly in the instances, the average passenger waiting time in the TFS is 60.1 min. For this confguration of passenger waiting time reduced from 15.4 min with limited detours to 13.7 min, 11% shorter. Te in-vehicle time was a the network and instances, the MA could be able to reduce bit longer, on average 16.6 min per passenger compared to this waiting time by 21% to 47.2 min. Te in-vehicle time was 17.9 min with the limited detours (7.8% longer). An oper- reduced by 13%, from 41.0 min on the TFS to 35.5 min on ation period example for this unrestricted detour analysis is the DRFS. Te average computation time for this network presented in Appendix D. As before, increasing the was 459 seconds. Te gain on this network was smaller than 16 Journal of Advanced Transportation Table 9: Average passenger waiting, in-vehicle, and travel time for policy, and 53.5% with the unrestricted detour policy. 60 instances comparing limited detour policy and unrestricted However, the computation time increased from 56 to movements for the lines. 459 seconds to optimize one operation period. Tese results prove that a semifexible DRFS allowing limited detours can 2 stops detour Unrestricted Improvement provide a good solution in a faster time than a fully fexible p p p p p p p (%) tt tt tt wt vt wt vt DRFS. Despite somewhat long computation times, typical 30% empty for evolutionary algorithms that perform a random explo- 15.9 16.9 32.8 14.6 18.2 32.8 0.00 stops ration of the search space, these results also confrm the good 50% empty 15.7 16.6 32.4 13.7 18.1 31.7 2.20 performance of the MA. stops When evaluating the same instances with the DRFS 70% empty 14.7 16.4 31 12.8 17.3 30 3.30 obtained by the MA, and comparing it with the results of the stops same instances in the TFS, the average passenger waiting Average 15.4 16.6 32.1 13.7 17.9 31.5 1.70 time reduced with 31.4%, 48.1%, and 57.7% for the same network with two, three, and four lines, respectively. Despite slightly increasing the passengers’ in-vehicle time with 0.6%, Table 10: Average passenger waiting, in-vehicle, and travel times 0.6%, and 8.4%, respectively, the total travel time for the for TFS, and the solution of the MA for the DRFS considering the DRFS is always smaller than in the TFS. Tis reduction varies large network. between 6% and 73%. Another characteristic of of-peak operations, which are TFS solution MA solution Improvement the focus of this DRFS, is that there are a lot of empty bus p p p p p p p (%) wt vt tt wt vt tt tt stops along the routes. Tis feature is explored in these 30% empty experiments by categorizing the instances according to the 59.5 41 100.5 47.8 37 84.8 15.6 stops percentage of empty stops during the operation horizon. 50% empty 60.4 41 101.4 47.9 36.2 84.2 17.0 Increasing the percentage of empty stops in an instance, stops from 30% over 50% to 70% increased the benefts of the 70% empty 60.4 41 101.3 45.8 33.2 79.1 22.0 DRFS. For the same network, the average passenger travel stops time reduced with 28.2%, 29.6%, and 34.0% for these Average 60.1 41 101.1 47.2 35.5 82.7 18.2 clusters, respectively. In the network with 70 bus stops and three lines, the average passenger travel time reduced with 15.6%, 17.0%, and 22.0%, respectively. Tese results confrm the previous network, where lines could better “assist” other the efciency of the DRFS in low-demand of-peak opera- lines by taking over bus stops. In this larger network, stop tions. Te overall gains, however, are dependent on the skipping is not always used due to the unavailability of other network confguration and the line characteristics, as well as lines to take passengers from the skipped stops. Still, sig- the potential for shortcuts. nifcant improvements of on average 18.2% were obtained. Te results presented in this paper demonstrated the benefts of operating a DRFS to substitute a TFS. As such, it could be used to improve efciency of transit system in 6. Conclusion and Future Research suburban areas. However, the presented DRFS could be Tis paper presents a semifexible demand-responsive feeder further improved. For instance, by allowing buses to arrive at the station or depart from the terminal outside the operation system (DRFS) as a substitute to a traditional feeder system in suburban area. Te semifexible DRFS runs a service period and by cancelling services without passengers, the similar to a traditional feeder system (TFS), but with ad- frst situation can also be observed in the results in Appendix justable routes and timetables according to passengers’ re- B, where requests arriving late in the period are served quests. Its objective is to optimize passenger travel time. during the following period only. Allowing buses to arrive at the hub station after the operation period has fnished could From the operators’ perspective, the proposed system allows to ofer a more fexible system to the passengers using the improve the operation and increase the responsiveness of the system. However, it also means these buses might not be same resources. It does require a reservation system where passengers can make requests. available on time for the next operation period. Tis future implementation, however, would change the characteristic In order to optimize the operations of the DRFS, a memetic algorithm (MA) is developed, merging an evolu- of the system from static to more dynamic, with a rolling tionary metaheuristic with local search operations. Te re- horizon operation period and the possibility to reoptimize sults of the MA were found to have a travel time of the system when new requests arrive and some services are 0.1 minute longer than the optimal solution. Moreover, the already in operation. Tis approach is considered as future results of the MA were the same as in the optimal solution research. for seven out of ten periods. Also, as mentioned in the results in Section 5.4, the bus routes are not optimized when the buses are not carrying When comparing the performance of the DRFS, opti- mized with the MA, to the TFS for a network composed of 25 passengers, which might lead to unnecessary detours. Terefore, an improvement could be to modify the objective bus stops and three lines, the DRFS reduced the average passenger waiting time by 48.8% with the limited detour function value to remove these needless detours. It means Journal of Advanced Transportation 17 areas,” Journal of Transport Geography, vol. 88, Article ID optimizing the operation from the passengers’ perspective 102859, 2020. and from the operator’s perspective, aiming to ofer an [7] F. Bruzzone, M. Scorrano, and S. Nocera, “Te combination of efcient operation in terms of vehicle kilometers as well. e-bike-sharing and demand-responsive transport systems in Another limitation of the current DRFS is that it considers rural areas: a case study of Velenje,” Research in Trans- only the trips towards the hub station. Transfer times for portation Business & Management, vol. 40, Article ID 100570, passengers at the hub station are not considered, assuming a high frequency service from this point. In practice, hub [8] R. Mounce, S. Wright, C. D. Emele, C. Zeng, and J. D. Nelson, stations concentrate several diferent line services, and “A tool to aid redesign of fexible transport services to increase transfer time coordination plays a crucial role to improve efciency in rural transport service provision,” Journal of passengers’ experience using public transport. Synchroniz- Intelligent Transportation Systems, vol. 22, no. 2, pp. 175–185, ing these services at the station, as covered by Barabino et al. [26], and considering the transfer time at the station, as well [9] C. Bellini, G. Dellepiane, and C. Quaglierini, “Te demand as implementing a bi-direction service could improve the responsive transport services: Italian approach,” WIT service ofered by the semifexible DRFS and increase the Transactions on Te Built Environment, vol. 64, WIT Press, success of such a system. Ashurst Lodge, Southampton SO40 7AA, UK, 2003. [10] M. Diana, L. Quadrifoglio, and C. Pronello, “A methodology for comparing distances traveled by performance-equivalent Data Availability fxed-route and demand responsive transit services,” Trans- All instances and detailed results are made available at portation Planning and Technology, vol. 32, no. 4, pp. 377–399, https://www.mech.kuleuven.be/en/cib/drbp/. 2009. [11] Z. N. Kashani, N. Ronald, and S. Winter, “Comparing demand responsive and conventional public transport in a low de- Conflicts of Interest mand context,” in Proceedings of the 2016 IEEE International Te authors declare that they have no conficts of interest. Conference on Pervasive Computing and Communication Workshops (PerCom Workshops), pp. 1–6, IEEE, Sydney, NSW, Australia, March 2016. Acknowledgments [12] C. Archetti, M. G. Speranza, and D. Weyland, “A simulation Tis project was supported by Internal Funds KU Leuven study of an on-demand transportation system,” International Transactions in Operational Research, vol. 25, no. 4, (Project no. C24M/19/055). pp. 1137–1161, 2018. [13] R. J. R. Gomes, Dynamic Vehicle Routing for Demand Re- Supplementary Materials sponsive Transportation Systems, Doctoral dissertation, Uni- versidade do Porto – Portugal, Porto, Portugal, 2012. Appendix A: a mathematical model of a (simplifed) [14] P. Vansteenwegen, L. Melis, D. Akta¸, s B. D. G. Montenegro, semifexible Demand-Responsive Feeder System. Appendix F. Sartori Vieira, and K. Sorensen, ¨ “A survey on demand- B: an example result for one instance and discussion. Ap- responsive public bus systems. Transportation Research Part pendix C: layout of the network used for the instances and C: emerging,” Transportation Research Part C: Emerging the traditional fxed lines. Appendix D: an example solution Technologies, vol. 137, Article ID 103573, 2022. of the MA with unrestricted routes. (Supplementary [15] Y. Zheng, W. Li, and F. Qiu, “A methodology for choosing Materials) between route deviation and point deviation policies for fexible transit services,” Journal of Advanced Transportation, References vol. 2018, Article ID 6292410, 12 pages, 2018. [16] B. D. Galarza Montenegro, K. Sorensen, ¨ and [1] J. L. Schofer, B. L. Nelson, R. Eash et al., TCRP Report 98: P. Vansteenwegen, “A large neighborhood search algorithm Resource Requirements for Demand-Responsive Trans- to optimize a demand-responsive feeder service,” Trans- portation Services, Transportation Research Board, Wash- portation Research Part C: Emerging Technologies, vol. 127, ington DC, 2003. Article ID 103102, 2021. [2] C. Mulley and J. D. Nelson, “Flexible transport services: a new [17] J. Zhang, D. Z. W. Wang, and M. Meng, “Analyzing cus- market opportunity for public transport,” Research in tomized bus service on a multimodal travel corridor: an Transportation Economics, vol. 25, no. 1, pp. 39–45, 2009. analytical modeling approach,” Journal of Transportation [3] S. C. Ho, W. Y. Szeto, Y. H. Kuo, J. M. Leung, M. Petering, and Engineering, Part A: Systems, vol. 143, no. 11, Article ID T. W. Tou, “A survey of dial-a-ride problems: literature review 04017057, 2017. and recent developments,” Transportation Research Part B: [18] Y. Lyu, C. Y. Chow, V. C. Lee, J. K. Ng, Y. Li, and J. Zeng, “CB- Methodological, vol. 111, pp. 395–421, 2018. Planner: a bus line planning framework for customized bus [4] C. Iliopoulou and K. Kepaptsoglou, “Combining ITS and systems,” Transportation Research Part C: Emerging Tech- optimization in public transportation planning: state of the art nologies, vol. 101, pp. 233–253, 2019. and future research paths,” European Transport Research [19] R. Guo, W. Guan, W. Zhang, F. Meng, and Z. Zhang, Review, vol. 11, no. 1, pp. 27–16, 2019. “Customized bus routing problem with time window re- [5] A. Verma and S. L. Dhingra, “Developing integrated schedules strictions: model and case study,” Transportmetrica: Trans- for urban rail and feeder bus operation,” Journal of Urban Planning and Development, vol. 132, no. 3, pp. 138–146, 2006. portation Science, vol. 15, no. 2, pp. 1804–1824, 2019. [20] X. Li and L. Quadrifoglio, “Feeder transit services: choosing [6] M. Borjesson, ¨ C. M. Fung, and S. Proost, “How rural is too rural for transit? Optimal transit subsidies and supply in rural between fxed and demand responsive policy,” Transportation 18 Journal of Advanced Transportation Research Part C: Emerging Technologies, vol. 18, no. 5, pp. 770–780, 2010. [21] H. Yang, Z. Zhang, X. Liang, M. M. Abid, W. Fan, and L. Pu, “Optimal service design of demand responsive connector with elastic demand,” in Proceedings of the 2019 5th International Conference on Transportation Information And Safety (ICTIS), pp. 945–950, IEEE, Liverpool, UK, July 2019. [22] S. M. Nourbakhsh and Y. Ouyang, “A structured fexible transit system for low demand areas,” Transportation Research Part B: Methodological, vol. 46, no. 1, pp. 204–216, 2012. [23] K. Uchimura, H. Takahashi, and T. Saitoh, “Demand re- sponsive services in hierarchical public transportation sys- tem,” IEEE Transactions on Vehicular Technology, vol. 51, no. 4, pp. 760–766, 2002. [24] A. Pratelli, M. Lupi, A. Farina, and C. Pratelli, “Comparing route deviation bus operation with respect to dial-a-ride service for a low-demand residential area,” Data analytics, vol. 45, p. 151, 2018. [25] E. Vermeir, W. Engelen, J. Philips, and P. Vansteenwegen, “An exact solution approach for the bus line planning problem with integrated passenger routing,” Journal of Ad- vanced Transportation, vol. 2021, pp. 1–18, Article ID 6684795, [26] B. Barabino, M. D. Francesco, G. Maternini, and S. Mozzoni, “An ofine framework for the diagnosis of transfer reliability using automatic vehicle location data,” IEEE Intelligent Transportation Systems Magazine, vol. 14, no. 4, pp. 163–182,

Journal

Journal of Advanced Transportation – Hindawi Publishing Corporation

Published: Feb 15, 2023

There are no references for this article.