nickolasclarke / dispatch Goto Github PK

placeholder

somewhat the inverse of #21 . If there is a particularly long route, we may get into an infinite loop of creating buses to serve that route.

As first step, we should flag the route and skip. As a second step, we should maybe break the route up? This will be important when we point this at a regional inter-city bus system.

@r-barnes I had a few minutes to move filtering to the parser (and control for all types of non-bus routes), and re-run with some different values based on the email convo. I saw a need for only ~1200 buses with this configuration.

I also sat down and read through the bulk of the documentation for salabim. Aside: some of the most clearly written examples I've seen, really easy to follow and remarkably simple). I now have a better grasp on the mechanics. It seems that currently while we are only using a "centralized" charger, that that charger effectively has an unlimited number places to charge, and is only constrained on total energy available correct? Any bus that is out of power and is returned to the depot begins charging, correct?

If so, my thoughts on next before we can hop on a call with the LBL team:

• add a queue for the depot for a limited number of spots to facilitate charging.
• next add multiple depots and give each their own queue. No need to give their own energy resource.
• do some sort of analysis to find common termini (probably sort for frequency of stop_ids?) to determine how many depots to create?

I'm not quite sure how to tackle the spatial placement of these depots in the sim. Currently the buses dont any sense of space in the sim, In our current arrangement, what are your thoughts on how to approach adding this?

parse_gtfs is very brittle right now. It essentially only works for Minneapolis. I will work through a battery of other feeds of varying quality to determine where it needs more flexibility. This will likely result in a few other issues, but I'll keep this branch for general work.

Currently we fix the drive train efficiency. We should make more accurate estimates of the route efficiency in both directions of travel based on the elevation profile of the route.

https://github.com/Dungyichao/Electric-Vehicle-Route-Planning-on-Google-Map-Reinforcement-Learning has simple physical model of how this might work.

right now we allow for all the buses in a depot to charge simultaneously. This is likely not accurate.

Expected outcome:

1. a bus is created and assigned to the block. its energy reserves and its starting depot_id are noted.
2. Before any trip starts, a bus evaluates if it has enough energy to serve the
   full trip to its final destination.
3. If it does have enough energy it completes the trip,substracting the energy
   required to serve the trip from its energy reserves.
   • If a charger is present at the termini where it completes its trip, the
     bus will opportunistically charge until it has to depart for its next
     assigned trip.
4. It repeats this process until one of the following:
   • If it does not have enough energy, the bus returns to the starting depot,
     and another fully charged bus replaces it. This bus has no starting depot, as it starts in the middle of the block. It follows steps 1-4.
   • If it completes its block, it returns to the nearest depot and charges.

Current outcome:

1. Buses are reassigned before finishing blocks
2. buses return to the depot before finishing the block and then return to serve the block.

Further details:
Details about Block_id: 93217702 in AC Transit, scenario 220kwh battery, 500kw nondepot chargers.

See this trips file. Strip the .log filetype after downloading, since GH doesnt permit .csv

Intro:
This block has 3 buses that are used to complete the block: 672, 673, and 674.

First, lets see a summary of all trips in the block. We can see here that we start with bus 672, which leaves from depot 3 and performs a single trip. It then gets reassigned to another block (see details about the bus below) and is replaced by 673. 673 Continues the block until it is out of energy. Once it is out of energy, it returns to depot 3, charges fully (! this is surprising) and then completes one trip. Then Bus 674 takes over, and completing 3 trips and then returning to depot 3. The block is complete.

opti_trips = pd.read_csv('actransit/220kwh_500_kw_trips.csv', index_col=0)

opti_trips[opti_trips['block_id'] == 93217702].sort_values('end_arrival_time')[['bus_id','end_arrival_time','start_arrival_time','start_depot_id','end_depot_id','end_stop_id','start_stop_id','energy_left','distance']]

Next lets look at what each of the buses themselves do. First up, Bus 672:

This bus starts on the block detailed above for one trip. It then gets reassigned to another block, 93217602. (why?) It then serves three trips for that block, completing the block and returning to the depot 3, nearly fully charged.

opti_trips[opti_trips['bus_id'] == 672].sort_values('end_arrival_time')[['block_id',      'end_arrival_time','start_arrival_time','start_depot_id','end_depot_id','end_stop_id','start_stop_id','energy_left','distance']]

Next Bus 673: Since 672 is reassigned, 673 picks up. Since it starts in the middle of the block, it does not have a starting depot listed. It travels to the start of the next trip in the block and continues to serve those trips until it no longer has enough energy to serve the next trip. It returns to depot 3 and charges fully (this is unexpected) then returns to finish the block. I need to dig more to see if it actually meets the required starting time of the next trip in the block, given that it has time to return and fully charge. It then serves one additional trip in the block, then returns to the depot before block has been completed, almost fully charged. It is not deployed again.

opti_trips[opti_trips['bus_id'] == 673].sort_values('end_arrival_time')[['block_id',   'end_arrival_time','start_arrival_time','start_depot_id','end_depot_id','end_stop_id','start_stop_id','energy_left','distance']]

And finally Bus 674:

Since bus 673 returns to the depot, bus 674 is assigned. It, however, does have a starting depot unlike 673 did. (why?) It continues to serve the remaining trips in the block, and then once the block is complete, it returns to the depot.

opti_trips[opti_trips['bus_id'] == 674].sort_values('end_arrival_time')[['block_id',       'end_arrival_time','start_arrival_time','start_depot_id','end_depot_id','end_stop_id','start_stop_id','energy_left','distance']]

A script to download all GTFS feeds from Transit Feeds, validate feed, filter for feeds that include buses, and attempt to run parse_gtfs.py against the feed.

See: https://github.com/RoutingKit/RoutingKit/blob/master/doc/ContractionHierarchy.md

for future.

block_id is an optional field in the GTFS spec. In order to run against all GTFS feeds, we'll need to refactor to build our own block_id or otherwise on feeds without.

1. Check that road segments are not unique and shared by trips (and ideally overlapping routes as well).

• pull in the shape file
• group by shape_id, this breaks the dataframe into small dfs for each shape_id
  • do an adjacent pairwise iteration over all the lat/lngs
  • take pairwise into 4 tuple of origin dest lat/longs, put into hash table and see how often they show up. Should probably be > than 1 since a given route is probably driven more than once a day.
    build a histogram of usage so we can wee which road segments that are not termini are best suited have en-route charger. This may be difficult to do with lots of overlapping termini and tight road segments

2. If the road segments are shared, count the number of buses that pass through.

We should include additional limits on depth of discharge of the Bus batteries. See M. McCall's EV trucking paper appendix data for more details.

Currently, if you follow the build instructions on Fish shell, it incorrectly parses the pwd append in the CMAKE command as part of the build instructions. This leads to a '`pwd' directory and various files missing from the /build/bin directory

1. pre-processing (outside of walk_route())

• calculate the cumulative distance for each of shape_ids
  • use geopandas to sum the distance of the shapefile
  • append this distance to each trip as trip_dist

2. Walk a trip

• for a trip passed to walk_route, pull trip.trip_dist, convert to an energy_req, and subtract from bus['energy']
• if the destination termini has a nearby_charger than check if the time before the next required departure (trip index + 1 in trips) is less than some threshold. If so, than charge at some given rate self.charge_rate and append that energy value back to bus['energy']. If there is no nearby charger, than return and the loop will continue, attempting to serve the next trip.

Currently we use a fixed charge rate (default of 150 kw) regardless of the battery State of Charge (SoC). This does not match reality and will give us inflated charge values.

Create some pretty pictures and other analysis for each feed's results. Initial work based off analysis I did for PP275.

The following line is should exclusive, instead of inclusive. Not all GTFS feeds will have this same set of columns.
trips = trips.drop(columns=[ . . .

the final pickle still has ~500 trips with RAIL in the trip_id string. I'm having trouble determining where they are introduced.

validating on the df at this point suggests that there are no RAIL trips left. However, when I load the final pickle, there are many trips with RAIL. I also tried searching in the df at line 48 above for one of the integer IDs in the trip_id string from the final pickle, such as 15269175 from 15269175-AUG19-RAIL-Weekday-01 and its also not present. We seem to be introducing additional trips somewhere.

Basic Costs / Inputs:

• Base Bus (w/out batteries):$550k
• Battery Kwh: $100 (current), $50 (future)
• DCFC Charger (opportunistic, probably quite low density)
  • Rate: 500kw
  • Cost: ~$600k NREL, pg 5
• In Depot Charger:
  • Rate: 125kw
  • Cost: ~$50k
  • note: we don't have logic to decide how many chargers are needed per depot
• Bus Efficiency: 1.1 kwh/km

Archived Version

Modeling Objective:
Minimize the cost of an EV bus deployment

Optimization

min $\sum^{n}_{i=1}x_i$ subject to $g_i(x)$ and $h_j(x)$

Decision Variables

The decisions the model is making, in order to minimize our costs.

• # of Buses
  • $550,000 w/out batteries (proterra CEO 2019)
• Kwh of battery per bus
  • ~$100 - $150 BNEF
  • could be fun to model with lower prices as well.
• # of chargers
  • this is dependent on the discussion about charging rate. see below.
• # of depots
  • This is also dependent on discussion of charging rate. Also this may simply be a equality constraint

These are all discrete integers, but I think that they could be treated as continous and simply round up to the nearest int value.

Inequality Constraints (a ranged constraint) $g(x)$

note: I think all of these could be set as equality constraints instead, and addressed through scenarios

• min/max of kwh per battery
  • $E_{bat} \ge 0 \le 660$
  • BYD: ~450 kwh
  • Proterra: ~660 kwh
  • could be interesting to raise this for future projected energy densities?
  • alternative min could be the lowest commercially available bus battery size. This would make the cost of a bus vs kwh easier to estimate based off of public data.
• density of chargers across termini
  • $\rho_{term}$
  • this is highly subjective. Right now, we site chargers based on "popularity" of the route at an arbitrary level of >= 100 discrete bus trips through the termini at a time. There are two main options in my mind now:
    • 1. Continue with some subjective level, either absolute (>=100 trips at a termini), or a percentage of total system trips threshold (5%? 10%?)
    • 2. make this the decision variable instead of # of chargers, could likely be unbounded. Would require a spatial optimization as well though. Also would have to be done before running the model? This seems complicated and somewhat convoluted, though perhaps more accurate.
      • Perhaps instead this becomes an equality constraint at a fixed level and we include different levels in the various scenarios described further below.

Equality Constraints (fixed constraint) $h(x)$

• charging rate @ termini chargers
  • possible range: $P_{term} \ge ~100 \le ~240$
  • Further discussion needed. We could make the argument for having low density but high power capacity chargers, while depots have slower chargers. (this probably matches closer to how fleets would actually be operated, I think)
• charging rate @ depot
  • possible range: $P_{dep} \ge 100 \le 500$
  • Proterra bus ranges
  • Proterra charger ranges
• must serve all trips
• all trips must be served at the exact time
• Bus energy >=0 (is this needed?)
• $E_{bus}$
• drivetrain efficiency (see proterra specs sheets)
  • $\eta_{dt} \ge 1.5 \le 2.3$
  • We could simply fix this with no high/med/low. Probably most prudent.

Scenario runs

For each feed, the model should be run with a minimum of high/medium/low values for the relevant equality constraints. This would result in a combinations table of all possible scenarios. We can add more nuance to this 3

cite

Generate trips only builds for route_type = 3

It should use the route_types outlined in

At the end of each trip, a bus should charge for the time in between the end and start of the next trip - a slight penalty for plugging/unplugging.

found while investigating #89, using the same scenario and data. See that ticket for the csv used.

Expected results:

1. Bus is created with 220 kwh, and can only charge to 220kwh max.
2. Bus only serves 1 trip at at time.

Observed Results:
In this scenario Bus 767 appears to start with significantly higher power than 220kwh (assuming energy left is in units kwh) It also continues to overcharge, over 2000kwh at its peak. It also serves two trips with the same start/end arrival_time fields, one of which starts from a depot, another of which starts in the middle of a block. This suggests it serves two trips at at time.

opti_trips = pd.read_csv('actransit/220kwh_500_kw_trips.csv', index_col=0)
opti_trips[opti_trips['bus_id'] == 767].sort_values('end_arrival_time')

I noticed that some lines in minneapolis still had the RAIL prefix in their trip title, (15269175-AUG19-RAIL-Weekday-01, which is the 901-112) but are classified as a bus in GTFS. This is because they are trollybuses, with electrified overhead lines. While not strictly necessary, it may be worth adding a filter flag for these in parse_gtfs in the future.

• Cost per bus:
  • Base cost of bus (driver hourly rate + some base cost of a bus (minimum battery size?)
  • cost per additional kwh of battery capacity
    • we should cap max kwh of battery size, to account for volumetric limitations that would be reached in reality.
• Cost per level 2 charger
  • could be a flat value of a charger with installation
  • stretch goal includes T+D changes that would need to happen
• Cost per level 3 charger depot (?)
  • could be a flat value of a charger with installation
  • stretch goal includes T+D changes that would need to happen

This should then be used to do a basic fiscal optimization to find the least cost solution for a given transit network. I envision this including kwh and and level 2 charger penetration (as a function of the total termini in the system) as either tuneable parameters, or inputs into a more traditional optimization cost function.

It seems if we have just a single depot, that a cost minimization optimization should be fairly straightforward? Otherwise, crafting several scenarios of something like high / med / low kwh capacity coupled with high / med / low level-2 charger penetration and brute forcing through a number of scenarios should give a good idea of what is possible without solving the formal optimization.

1. Remove the ABM stuff
   • remove charger queues, etc.
2. Figure out a way to walk through a block of trips
   • send buses to and from depots until the block is exhausted

We currently charge linearly and at full rate from 0% SoC to 100%. This is inaccurate.

somewhat related to #21 and #22. Currently once a block is completed, that bus is no longer considered for use. Currently we assume a block should occupy a bus for an entire day. However, in my cursory analysis of Minneapolis blocks, some of these appear to be rather short, and these buses would be idle.

Furthermore, in my analysis of both the processed GTFS feed dataframes fed into the sim, and the results, it appears that, according to our current calculations, Minneapolis should require ~1554 buses to simply meet all the blocks. But according to Metro Transit they only have 909 buses in their fleet. This further suggests that blocks do not cover a full day. I'll do further analysis of this later.

My initial impressions on how to deal with this would be to be to add some logic in Model.run() of sim and run_block() to release a bus to a queue that can be used by later call of run_block(), otherwise create a new bus.

I think the parallelism could in Model.run() could cause some extraneous bus creation. We may sort the blocks by total block duration, instead of earliest start time, but I don't think this covers it entirely still. This parallelism edge case may not be worth considering, given our rough overall accuracy anyhow.

update readme with more detailed install and build instructions.

optimize_bus_distribution.py currently gives a very low number (99 buses req. to service AC transit, for example)

output when attempting to parse the latest minneapolis gtfs feed.

Traceback (most recent call last):
  File "parse_gtfs.py", line 234, in <module>
    road_segs, seg_props = GenerateRoadSegments(ptg.load_geo_feed(feed_file))
  File "parse_gtfs.py", line 202, in GenerateRoadSegments
    shape_props['distance'] = [[SegLength(*x) for x in x] for x in shape_props['seg_hash']]
  File "parse_gtfs.py", line 202, in <listcomp>
    shape_props['distance'] = [[SegLength(*x) for x in x] for x in shape_props['seg_hash']]
  File "parse_gtfs.py", line 202, in <listcomp>
    shape_props['distance'] = [[SegLength(*x) for x in x] for x in shape_props['seg_hash']]
  File "parse_gtfs.py", line 184, in SegLength
    xd = p1[0]-p2[0]
TypeError: 'float' object is not subscriptable

plenty of feeds that otherwise should be supported are not parsed. This is a placeholder to resolve all of these issues.

currently we run each block of trips in series, but they can be run in parallel.

There may be short blocks that take less energy, in total, than a bus starts with. These buses fall through the cracks, I think.

When I run minneaplolis with the default inputs, I encounter many energy traps (where the bus does not have enough energy to return to depot), and seemingly leads to a segfault. I've also bumped up the default value to 300 kwh of battery_cap and it also seg faults. I don't immediately see an issue in the lines that may cause this, they should account for this edge case.

reproduce with the following inputs:

julia --project ./sim.jl ../../data/parsed_minneapolis ../../data/minneapolis-saint-paul_minnesota.osm.pbf ../../data/depots_minneapolis.csv minneapolis_out

Energy trap found!
Energy trap found!
...
Energy trap found!
Energy trap found!
..................
signal (11): Segmentation fault
in expression starting at /mnt/c/Users/nicko/repos/dispatch/build/bin/sim.jl:329
unknown function (ip: 0x7f880c204d17)
unknown function (ip: 0x7f880c205070)
__gxx_personality_v0 at /usr/bin/../lib/x86_64-linux-gnu/libstdc++.so.6 (unknown line)
unknown function (ip: 0x7f880c0006ee)
_Unwind_Resume at /lib/x86_64-linux-gnu/libgcc_s.so.1 (unknown line)
getTravelTime at /home/nclarke/winhome/repos/dispatch/build/../src/routingkit/routingkit.cpp:69
operator() at /home/nclarke/.julia/packages/CxxWrap/lDNAy/deps/usr/include/jlcxx/module.hpp:981 [inlined]
_M_invoke at /usr/include/c++/9/bits/std_function.h:286
operator() at /usr/include/c++/9/bits/std_function.h:688 [inlined]
operator() at /home/nclarke/.julia/packages/CxxWrap/lDNAy/deps/usr/include/jlcxx/module.hpp:47 [inlined]
apply at /home/nclarke/.julia/packages/CxxWrap/lDNAy/deps/usr/include/jlcxx/module.hpp:72
getTravelTime at /home/nclarke/.julia/packages/CxxWrap/lDNAy/src/CxxWrap.jl:552
TimeDistanceBetweenPoints at /mnt/c/Users/nicko/repos/dispatch/build/bin/sim.jl:53
FindClosestDepotByTime at /mnt/c/Users/nicko/repos/dispatch/build/bin/sim.jl:230
RunBlock at /mnt/c/Users/nicko/repos/dispatch/build/bin/sim.jl:84
Model at /mnt/c/Users/nicko/repos/dispatch/build/bin/sim.jl:201
main at /mnt/c/Users/nicko/repos/dispatch/build/bin/sim.jl:310
unknown function (ip: 0x7f881048ef7c)
unknown function (ip: 0x7f881048ec49)
unknown function (ip: 0x7f881048f0b0)
unknown function (ip: 0x7f881048f668)
unknown function (ip: 0x7f881048fe8f)
unknown function (ip: 0xfffffffffffffffe)
unknown function (ip: 0x7f87dda9a08f)
unknown function (ip: 0xffffffffffffffff)
unknown function (ip: 0x7f881049025e)
unknown function (ip: 0x7f8810370276)
unknown function (ip: 0x7f881034e7ad)
jl_load at /usr/bin/../lib/x86_64-linux-gnu/libjulia.so.1 (unknown line)
include at ./boot.jl:328 [inlined]
include_relative at ./loading.jl:1105
include at ./Base.jl:31
exec_options at ./client.jl:287
_start at ./client.jl:460
jfptr__start_2084.clone_1 at /usr/lib/x86_64-linux-gnu/julia/sys.so (unknown line)
unknown function (ip: 0x7f8810862755)
unknown function (ip: 0x7f8810862332)
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7f88108623d9)
Allocations: 172195181 (Pool: 172176543; Big: 18638); GC: 141
fish: “julia --project ./sim.jl ../../…” terminated by signal SIGSEGV (Address boundary error)