# Dynamic Demand-Responsive Feeder Bus Network Design for a Short Headway Trunk Line
## 3 Methodology
### Algorithm  
The DRTTW problems are combinatorial, and encountering multiple local optima is expected. This study employs the SA algorithm due to its capability to escape local optima by accepting sub-optimal solutions. Moreover, given the problem's nature, the SA algorithm can efficiently navigate a vast solution space, offering flexibility to explore and, through iterative refinements, achieve a near-optimal solution within a reasonable timeframe. The SA algorithm starts with a random solution and an initial high temperature. As iterations progress, the temperature decreases according to a cooling schedule. Convergence is determined by a set number of iterations and when temperature drops below a threshold. A cooling rate of 0.99 was chosen to ensure a gradual reduction in temperature, allowing the algorithm an extended exploration period before becoming more exploitative. Furthermore, the initial temperature was set at a sufficiently high value, enabling the algorithm to explore a broad spectrum of solutions from the outset. This strategy allows the SA algorithm to start with a more explorative approach, accepting even some suboptimal solutions to ensure it does not become trapped in local minima. When there are many passengers with different arrival time requests, meeting the exact train may not be so necessary, which means feeder buses can deliver the passengers any time as long as it is no later than their requested time. Although feeder buses can deliver passengers any time before the requested time, waiting time due to the early arrival should be included in the total travel time, and the maximum travel time ratio constraint should be met. Also, passengers cannot be picked up before their available departure time. To generate the initial solution, a random permutation with the length of \"number of passengers at the related station plus number of feeder buses minus one\" is produced. Then, depending on the location of greater numbers, the assignment of passengers to feeder buses is determined. For instance, in the presence of two feeder buses and 10 passengers, a permutation with length 11 is produced. Suppose that the generated permutation is as follows: Path = [10, 1, 3, 4, 8, 11, 2, 9, 5, 7, 6]. The path creator section was included in the model as a sub-algorithm. The next step is to define the routes of feeder buses. The feeder bus first picks up the first assigned passenger and continues picking up the others in turn. However, it would return to the station if its capacity is full. Also, it makes a comparison and returns to the station if the cost of the trip when returning to the station is less than the cost of continuing the route and picking up the next passenger. The feeder bus can also wait for the passenger to reach the passenger's allowed time to pick up based on the maximum acceptable time ratio. Furthermore, the feeder bus tries to return to the station before the requested times of its passengers. In each iteration, the algorithm tries to improve the solution by searching its neighborhoods. For this purpose, common swap, insertion, and reversion methods were used. The algorithm calculates the earliest and latest possible alighting/boarding time for each passenger. The latest alighting/boarding time is simply equal to the difference between arrival/departure time request and direct travel time (arrival/departure time request-direct travel time). In this stage, the algorithm assumes the feeder bus goes directly to the station right after alighting/boarding the passenger. In the next step, a series of passengers would be assigned to each vehicle, and new variables named \"updated latest alighting/boarding time\" would be introduced which are the latest possible alighting/boarding time for each passenger according to the defined series of passengers. This variable helps determine what series of passengers after serving a certain series should be served. Obviously, the updated latest alighting/boarding time will be equal to the latest alighting/boarding time for the last passenger.