Vehicle Routing Problem Public transport

TimSemmelhaack · ‎02-17-2013

I already modelled a vehicle schedule based on a given public transport timetable.
- I modelled all starts / ends of the timetable trip as orders with TimeWindowStart1 = TimeWindowEnd1 and DeliveryQuantities = 1 for the end and PickupQuantities = 1 for the start
- all routes / vehicles have the capacity 1

- I set the start of trip as the FirstOrderName and the end of the trip as the secondOrderName in the Table OrderPairs

And the end I get the number of vehicle to fulfill the given timetable and some figures like non-productive times/kilometers.

In the next step I want to vary the start/end time of each trip, but I want to keep the travel time of each trip (it's not possible/ too much effort to model the travel time with each stop / stopping time). The aim is to check if there a solution with less vehicles, if I vary stop/end time of the trips a little bit.

So my question: Is there a way to give each order pair (public transport trip) a fixed transit time? At the moment the order pairs only offer the parameter MaxTransitTime

NaAn · ‎02-20-2013

Hi,

You are solving an interesting problem with VRP solver. I like your idea. Here are some suggestions:

In your current solution, the vehicle has to fulfill one paired orders (a trip) before starting the next one. Therefore, the transit time for the paired orders is the shortest time between the first and second order in the pair. You can use the current transit time as the MaxTransitTime, which essentially is like a fixed transit time in this case.

In addition, please make sure the MaxViolationTime1 and MaxViolationTime2 are set to null for all orders so all time windows are soft restrictions. In the layer advanced settings, please choose the time window violations importance to low so there will be less penalty for time window violations. If you are free to set any time windows for those trips, I think you can remove all time windows to solve it. Solver will return you a lower cost solution with potentially less vehicles.

Thanks.

Anna

TimSemmelhaack · ‎02-25-2013

"In your current solution, the vehicle has to fulfill one paired orders (a trip) before starting the next one. Therefore, the transit time for the paired orders is the shortest time between the first and second order in the pair. You can use the current transit time as the MaxTransitTime, which essentially is like a fixed transit time in this case."
Because I simplify the public transport network it's not only the travel between the order pairs. I removed all intermediate stops so the travel time between the order pairs is much shorter than the real travel time of the trip. So I use the restricted time windows to model the real travel time. The picture shows the route in reality with a lot of deviations, so when I model only the first and the last stop I will create a shorter route on the direct connection.
A possibility would be to model all intermediate stops but this would take a lot of effort, and I had to put a lot more data in the model.

[ATTACH=CONFIG]22149[/ATTACH]

One result of this simplified bus routing and the hard restrictions is that the busses spend a lot on waiting time:
[ATTACH=CONFIG]22152[/ATTACH]

"In addition, please make sure the MaxViolationTime1 and MaxViolationTime2 are set to null for all orders so all time windows are soft restrictions. In the layer advanced settings, please choose the time window violations importance to low so there will be less penalty for time window violations. If you are free to set any time windows for those trips, I think you can remove all time windows to solve it. Solver will return you a lower cost solution with potentially less vehicles."
I think I have to use hard restrictions because it's mainly school transport I model. We have some regulations that the whole travelling time (walking time to stop, time in the bus, waiting time at school before the class begins) is limited e.g. to 80 minutes and the start of school is fixed (is this scenario).

I think I do something with the VRP for which the tool wasn't made for, and I want to do a little more.

Update:
Probably a solution would be to add the waiting time which results from the strict time windows as a service time in the first or last stop of the order pair. Afterwards I can open the time window to model some scenarios.

NaAn · ‎02-27-2013

Because I simplify the public transport network it's not only the travel between the order pairs. I removed all intermediate stops so the travel time between the order pairs is much shorter than the real travel time of the trip. So I use the restricted time windows to model the real travel time. The picture shows the route in reality with a lot of deviations, so when I model only the first and the last stop I will create a shorter route on the direct connection.
A possibility would be to model all intermediate stops but this would take a lot of effort, and I had to put a lot more data in the model.

Could you please explain what the intermeidate stops are? Are those corresponding to other students pickup order pairs?

It looks like you are solving a standard bus tour problem where student pickups have time windows, stduents have restricted transit time on bus and students will be dropped off at school before school starts. If that's the case, the problem is easy to setup. You should use the bus seat number as the route capacity instead of 1. Load all student pair orders into one VRP layer and add more routes than it usually needs. For all order pairs:

Use the limit of "time in the bus" as the maxTransitTime

If you want to make a single visit to school, please make sure to use the same time window for the second order in all order pairs.

Solver will figure out a solution with the minimum number of vehicles to use for you.

Thanks.

Anna

MelindaMorang · ‎07-19-2013

Hello Tim. I just wanted to let you know about a new prototype tool from Esri's Network Analyst team which allows you to add GTFS public transit data directly to a network dataset. You can use this network dataset with the Network Analyst tools to run time-aware analyses that incorporate the transit schedules. This might be helpful for your study.
You can download the toolset and instructions here:
http://www.arcgis.com/home/item.html?id=0fa52a75d9ba4abcad6b88bb6285fae1
Please do not hesitate to contact me at mmorang@esri.com with questions or comments about this toolset.

TimSemmelhaack · ‎07-24-2016

Hi,

after a long time, I have done some further work on the problem. The approach with calculating the service time from the wait time works.

So you can do some scenario with different values for the MaxViolationTime. This can give some hints where you have bad connections between trips (Bus A arrives at 12:01 at Stop A, Bus B leaves at 12:00 at Stop A) or where you can create better connection between trips by extending the time between trips.

At the end you will probably have a lower number of vehicles or a better vehicle utilisation.

If someone is interested I can explain the procedure more in detail.

Tim