jamjpan / cargo Goto Github PK

View Code? Open in Web Editor NEW

28.0 5.0 8.0 3.74 MB

Real-time simulation library for ridesharing and other VRP problems

License: MIT License

C++ 13.28% Makefile 0.08% C 80.51% Python 0.48% AMPL 0.05% Shell 0.08% JavaScript 5.31% CSS 0.14% HTML 0.07%

vrp ridesharing

cargo's People

Contributors

Stargazers

Watchers

Forkers

yuchen-ecnu haidaoxiaofei masatoshihanai wbygit hamed-javidi bigmac0 ailsa99 bellyfat

cargo's Issues

Solve a small test case

Try to solve one of the test cases in benchmarks/cd1

The solution should be optimal (use an optimal algorithm)
~~Maybe we can allow a near-optimal solution for a large benchmark, instead of an optimal solution for a small benchmark. Why? Because the near-optimal solvers are easier to use than the optimal solvers~~

The format of the solution should be:

Instance name: cd1-SR-n10m5-<x>
Authors: your name
Date: dd.mm.yyyy hh:mm:ss
Reference: <none>
Solution
59823 meters
Veh 5: 2 3 7 8
Veh 9: 1 4
...
Route 5: (0, 4569) (3, 4570) ... (2110, 8127)
Route 9: (0, 8162) (20, 8163) ... (1260, 3807)

Explanation:
Line 1: "Instance name: " followed by the name of the instance being solved
Line 2: "Authors: " self-explanatory
Line 3: "Date: " self-explanatory
Line 4: "Reference: " followed by citation to where the solution is described (leave blank if none)
Line 5: The word "Solution"
Line 6: The cost of the solution (total distance traveled by the vehicles, plus the shortest-path distance of any unassigned customers), given in meters
Lines 7 -- (m+6): "Veh x: " where x is the vehicle ID, then followed by a list of customer IDs assigned to this vehicle
Lines (m+7) -- (2m + 7): "Route x: " where x is the vehicle ID following this route, then followed by a list of (t, i) tuples where t is the time the vehicle arrives at this node and i is the node ID.

Reference:

Using C/C++

SCIP (optimal)
GCG (optimal, generic branch-cut-price)
BCP (optimal)
SYMPHONY (optimal)
Symphony ref: https://dl.acm.org/citation.cfm?id=734759
Google OR tools (approximate??)
GLPK (optimal)

Seems to be easy to write models in GLPK. Not the fastest, but easy to use... and has wrappers in Python, Java, etc. https://spokutta.wordpress.com/the-gnu-linear-programming-kit-glpk/
Example python wrapper to make MathProg models, consumed by GLPK: http://pymprog.sourceforge.net/

Using Java
jsprit (approximate)

Example using Google OR tools:
https://developers.google.com/optimization/routing/tsp/vehicle_routing_time_windows
https://github.com/google/or-tools/blob/master/examples/python/cvrptw.py

Using MATLAB
https://github.com/Ivan-Zhou/Uber_Driver_Schedule_Optimization

Using R
https://dirkschumacher.github.io/ompr/

Using Julia
https://github.com/JuliaOpt/JuMP.jl

Using Python

SCIP seems to be best non-commercial solver
http://plato.asu.edu/talks/informs2017.pdf

Maybe use the academic version of Gurobi (free), has Python wrapper

If the problem instance is too hard (takes too long to compute), reduce the number of vehicles/customers, or tweak the instance... move the customers/vehicles closer together, tighten the time windows... etc. You can also try solving for just one vehicle (pick one vehicle, make the time window for the vehicle infinity, then ignore the other vehicles.. then the problem becomes Traveling Salesman Pickup and Delivery, TSPPD) If the solution is not interesting (no assignments), it's fine... because these are just test instances. We can make more interesting instances later.

The trip-grouping method needs an LP solver to do the trip-vehicle assignments. The solver should be fast... Cargo is written in C++, so maybe SCIP is the best choice. The problem is SCIP seems kind of hard to use. For the offline optimal solution, SCIP can be used through a wrapper like PySCIPOpt. But... GLPK has a very nice, clean, easy to use modeling language...

General Approach

Let origins and destinations be special nodes in the graph, call them "stops". Can we make the assumption that vehicles traveling between stops follow shortest-paths only? If that's the case, then we need O(n^2) decision variables, where n is the number of stops. Without this assumption, we will need O(|V|^2) decision variables, V is the set of nodes on the road network, and the problem model will become complicated. Well, I don't see how an optimal solution could possibly contain a path from stop u to v that is not the shortest path, so I think the assumption is correct. Then,

Step 1
Load up the problem instance; form the "reduced" problem graph by computing the matrix of travel cost from each stop to every other stop in the problem. Output from step1: an n x n distance matrix

Step 2
Model the problem; Let c[i][j] be the distance matrix from step 1; let there be k vehicles; the objective function is to minimize the total cost:
minimize sum(c[i][j]*x_k_i_j) for all combinations of i, j, and k
i = j = n; suppose a small benchmark has 10 customers, 5 vehicles, then there are 500 decision variables

Step 3
Model the problem; add constraints. Each stop has a time constraint.

rspgen producing infeasible problems

The problems from rspgen don't have good solutions. Use probplot to visualize the ones in data/benchmark. Just by eyeballing, it's obvious that the vehicles will not pick up any customers.

greedy_insertion crashing on rs-lg-5

Happened to me twice, but at different t. Time multiplier set to 5. Here is what I got the second time, at t=1597:

[2018-06-15 17:12:10][cargo] t=1597; stepped 228 vehicles; remaining=3221;
[2018-06-15 17:12:10][greedy_insertion] Match (cust17122, veh31399)
[2018-06-15 17:12:10][cargo] (5485 customers have timed out)
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 60) >= this->size() (which is 43)
[2018-06-15 17:12:10][cargo] Vehicle 25943 picked up Customer 4486(2217)
[2018-06-15 17:12:10][cargo] t=1598; stepped 227 vehicles; remaining=3221;

Thread 2 "greedy_insertio" received signal SIGABRT, Aborted.

Not sure which vector it's complaining about

Scheduling pseudocodes

Cost of a schedule

Route-through
Given a schedule, return the route through the schedule and its cost

int RouteThrough(const Schedule &s, Route &r) {
    Route r_;
    int c = 0;
    r_.push_back(s.front().node_id);
    for (auto i = s.begin(); i != std::prev(s.end()); ++i) {
        Route rt;
        gtree_.find_path(i->node_id, std::next(i)->node_id, rt);
        std::copy(std::next(rt.begin()), rt.end(), std::back_inserter(r_));
        c += gtree_.search(i->node_id, std::next(i)->node_id);
    }
    r = r_;
    return c;
}

Constraints checking

Precedence constraint: for any scheduled customer, the customer's origin is before the destination
Time window constraint: for all scheduled customers, time to destination is within late window

Precedence constraint checking O(n²)
Given a schedule, find if precedence is satisfied

check_precedence_constr(schedule) {
    if schedule.last.type is 'origin':
        return false
    for i from schedule.first to schedule.last:
        if i.type is 'origin':
            paired = false
        for j from schedule.first to schedule.last:
            if i == j: continue
            if i.customer == j.customer:
                if j.type is 'destination':
                    paired = true
                if (i < j && i.type is destination)
                    return false
        if !paired: # <-- there was an origin, but no destination
            return false
    return true
}

Time window checking O(n)
Given a schedule, find if time windows are satisfied
Assume there are methods to look up time windows, and to compute arrival times given a route

check_timewindow_constr(schedule) {
    if (arrival_time(route.last) > schedule.owner.late):
        return false;
    for i from schedule.first to schedule.last:
        if i.type is 'destination':
            if (arrival_time(i) > late(i))
                return false
    return true
}

Sequence-ordering

Brute-force enumeration O(n!)
Given a schedule, find the best ordering

# no elems in the schedule are fixed
sop_enumerate(schedule) {
    best_cost = inf
    best_route = null
    best_sch = null
    sort schedule lexicographically
    while schedule.has_next_permutation: # <-- this makes the algorithm O(n!)
        if (check_precedence_constr(schedule)):
            (cost, route) = route_through(schedule)
            if (cost < best_cost && check_time_constr(route)):
                best_cost = cost
                best_route = route
                best_sch = schedule
        schedule.next_permutation
    return (best_cost, best_route, best_sch)
}

Insertion O(n²)
Given a schedule and a customer, insert the customer in the best way

def sop_insertion(schedule, customer):
    schedule.insert(0, customer['origin']) # O(n)
    schedule.insert(0, customer['destination'])
    inc = 1
    reset = False
    for i in range(0, len(schedule)-1): # range does not include the last elem
        if inc == 1:
            start=i; end=len(schedule)-1
        else:
            start=len(schedule)-1; end=i+1
        for j in range(start, end, inc):
            if reset:
                schedule[i-1], schedule[i+1] = schedule[i+1], schedule[i-1] # O(1) (std::iter_swap, C++)
                reset = False
            else:
                schedule[j], schedule[j+inc] = schedule[j+inc], schedule[j]
            print(schedule) # <-- this is where route_through normally would go
        schedule[i], schedule[i+1] = schedule[i+1], schedule[i]
        if inc == 1 and i < len(schedule)-2:
            print(schedule) # <-- this is where route_through normally would go
        inc = -inc
        if inc == 1:
            reset = True

# Test
x = ['1o','1d','2o','2d','3o','3d']
c = {'origin': 'foo', 'destination': 'bar'}
sop_insertion(x,c)

where to find or generated the three additional files: {road}_nodes.js, {road}_positions.js, {road}_weights.js

vehicle is wrong after match

Before match, Vehicle 1 is at waypoint (0|0) (idx_lvn=0), with 1 dist left until the next waypoint.

After match, Vehicle 1 is now at (4|1) (idx_lvn=1), but with 3 dist until next waypoint (should be 4).
Schedule is 2 6, but should be 8 5 6
Load is still -2, should be -1

[2018-06-11 11:32:36][noname] Vehicle 1:
[2018-06-11 11:32:36][noname] origin     	0
[2018-06-11 11:32:36][noname] destination	6
[2018-06-11 11:32:36][noname] early      	1
[2018-06-11 11:32:36][noname] late       	19
[2018-06-11 11:32:36][noname] load       	-2
[2018-06-11 11:32:36][noname] nnd        	1
[2018-06-11 11:32:36][noname] route      	(0|0) (4|1) (7|2) (12|5) (15|6) 
[2018-06-11 11:32:36][noname] schedule   	1 6 
[2018-06-11 11:32:36][noname] idx_lvn    	0
[2018-06-11 11:32:36][noname] status     	1
[2018-06-11 11:32:36][cargo] new nnd: 0
[2018-06-11 11:32:36][greedy_insertion] Match (Customer 3, Vehicle 1)
[2018-06-11 11:32:36][greedy_insertion] best cost: 13
[2018-06-11 11:32:36][greedy_insertion] best route: (0|0) (4|1) (8|8) (14|5) (17|6) 
[2018-06-11 11:32:36][greedy_insertion] best schedule: 1 8 5 6 
[2018-06-11 11:32:36][cargo] t=4; stepped 2 vehicles; remaining=2;
[2018-06-11 11:32:36][cargo] (0 customers have timed out)
[2018-06-11 11:32:36][noname] Vehicle 1:
[2018-06-11 11:32:36][noname] origin     	0
[2018-06-11 11:32:36][noname] destination	6
[2018-06-11 11:32:36][noname] early      	1
[2018-06-11 11:32:36][noname] late       	19
[2018-06-11 11:32:36][noname] load       	-2
[2018-06-11 11:32:36][noname] nnd        	3
[2018-06-11 11:32:36][noname] route      	(0|0) (4|1) (8|8) (14|5) (17|6) 
[2018-06-11 11:32:36][noname] schedule   	2 6 
[2018-06-11 11:32:36][noname] idx_lvn    	1
[2018-06-11 11:32:36][noname] status     	1

low performance in step()

The largest benchmark has 10,920 vehicles; step() should be able to do all these in 1 sec to support real-time. Then 1,000 vehicles should be stepped in ~91 ms. But currently it takes 145 ms.

Example ./run_test with time_multiplier=10 on bj5 using rs-lg-4:

[2018-06-09 23:01:40][cargo] t=291; stepped 1000 vehicles; remaining=5711;
[2018-06-09 23:01:40][cargo] Elapsed (145 ms) exceeds interval (100 ms)

memory leak in example/greedy_insertion

Valgrind output:

==13659== HEAP SUMMARY:
==13659==     in use at exit: 190,468 bytes in 323 blocks
==13659==   total heap usage: 6,147 allocs, 5,824 frees, 1,252,309 bytes allocated
==13659== 
==13659== 4,104 bytes in 1 blocks are possibly lost in loss record 78 of 82
==13659==    at 0x4C2CB6B: malloc (vg_replace_malloc.c:299)
==13659==    by 0x45E923: sqlite3MemMalloc (sqlite3.c:21907)
==13659==    by 0x439158: mallocWithAlarm (sqlite3.c:25740)
==13659==    by 0x439158: sqlite3Malloc.part.3 (sqlite3.c:25770)
==13659==    by 0x439712: pcache1Alloc (sqlite3.c:47543)
==13659==    by 0x45CBB5: sqlite3PageMalloc (sqlite3.c:47682)
==13659==    by 0x45CBB5: allocateTempSpace (sqlite3.c:64192)
==13659==    by 0x45CBB5: btreeCursor (sqlite3.c:65879)
==13659==    by 0x45CBB5: sqlite3BtreeCursor (sqlite3.c:65921)
==13659==    by 0x4AF66B: sqlite3VdbeExec (sqlite3.c:84751)
==13659==    by 0x4BAF90: sqlite3Step (sqlite3.c:79607)
==13659==    by 0x4BAF90: sqlite3_step (sqlite3.c:79670)
==13659==    by 0x4AE61C: sqlite3_exec (sqlite3.c:114753)
==13659==    by 0x40D6EB: cargo::Cargo::initialize(cargo::Options const&) (cargo.cc:336)
==13659==    by 0x40F2AF: cargo::Cargo::Cargo(cargo::Options const&) (cargo.cc:69)
==13659==    by 0x4093BA: main (greedy_insertion.cpp:81)
==13659== 
==13659== 4,368 bytes in 1 blocks are possibly lost in loss record 79 of 82
==13659==    at 0x4C2CB6B: malloc (vg_replace_malloc.c:299)
==13659==    by 0x45E923: sqlite3MemMalloc (sqlite3.c:21907)
==13659==    by 0x439158: mallocWithAlarm (sqlite3.c:25740)
==13659==    by 0x439158: sqlite3Malloc.part.3 (sqlite3.c:25770)
==13659==    by 0x439712: pcache1Alloc (sqlite3.c:47543)
==13659==    by 0x43C21F: pcache1AllocPage (sqlite3.c:47639)
==13659==    by 0x43C21F: pcache1FetchStage2 (sqlite3.c:48105)
==13659==    by 0x479719: sqlite3PcacheFetch (sqlite3.c:46715)
==13659==    by 0x479719: getPageNormal (sqlite3.c:54573)
==13659==    by 0x430040: sqlite3PagerGet (sqlite3.c:54752)
==13659==    by 0x430040: btreeGetPage (sqlite3.c:63639)
==13659==    by 0x47A7F3: lockBtree (sqlite3.c:64593)
==13659==    by 0x47A7F3: sqlite3BtreeBeginTrans (sqlite3.c:64956)
==13659==    by 0x4BD779: sqlite3InitOne (sqlite3.c:119558)
==13659==    by 0x4BDAD9: sqlite3Init (sqlite3.c:119740)
==13659==    by 0x4BDB0F: sqlite3ReadSchema (sqlite3.c:119765)
==13659==    by 0x4BDC5D: sqlite3StartTable (sqlite3.c:104078)
==13659== 
==13659== 30,576 bytes in 7 blocks are possibly lost in loss record 81 of 82
==13659==    at 0x4C2CB6B: malloc (vg_replace_malloc.c:299)
==13659==    by 0x45E923: sqlite3MemMalloc (sqlite3.c:21907)
==13659==    by 0x439158: mallocWithAlarm (sqlite3.c:25740)
==13659==    by 0x439158: sqlite3Malloc.part.3 (sqlite3.c:25770)
==13659==    by 0x439712: pcache1Alloc (sqlite3.c:47543)
==13659==    by 0x43C21F: pcache1AllocPage (sqlite3.c:47639)
==13659==    by 0x43C21F: pcache1FetchStage2 (sqlite3.c:48105)
==13659==    by 0x479719: sqlite3PcacheFetch (sqlite3.c:46715)
==13659==    by 0x479719: getPageNormal (sqlite3.c:54573)
==13659==    by 0x430040: sqlite3PagerGet (sqlite3.c:54752)
==13659==    by 0x430040: btreeGetPage (sqlite3.c:63639)
==13659==    by 0x45C998: btreeGetUnusedPage (sqlite3.c:63783)
==13659==    by 0x47B191: allocateBtreePage (sqlite3.c:67634)
==13659==    by 0x4802E1: btreeCreateTable (sqlite3.c:70297)
==13659==    by 0x4802E1: sqlite3BtreeCreateTable (sqlite3.c:70316)
==13659==    by 0x4B202F: sqlite3VdbeExec (sqlite3.c:86824)
==13659==    by 0x4BAF90: sqlite3Step (sqlite3.c:79607)
==13659==    by 0x4BAF90: sqlite3_step (sqlite3.c:79670)
==13659== 
==13659== LEAK SUMMARY:
==13659==    definitely lost: 0 bytes in 0 blocks
==13659==    indirectly lost: 0 bytes in 0 blocks
==13659==      possibly lost: 39,048 bytes in 9 blocks
==13659==    still reachable: 151,420 bytes in 314 blocks
==13659==                       of which reachable via heuristic:
==13659==                         length64           : 137,272 bytes in 143 blocks
==13659==                         newarray           : 11,368 bytes in 1 blocks
==13659==         suppressed: 0 bytes in 0 blocks
==13659== Reachable blocks (those to which a pointer was found) are not shown.
==13659== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==13659== 
==13659== For counts of detected and suppressed errors, rerun with: -v
==13659== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)

Negative pickup delay

Run grabby on rs-bj5-m5k-c3-d6-s10-x1.0 to reproduce, get pickup delay is -3

multiple matches but only one pickup?

In this example, veh12 gets three assignments, but later it only makes one pickup/dropoff (cust13)???

[2018-06-13 00:28:33][greedy_insertion] Match (cust7, veh18)
[2018-06-13 00:28:33][greedy_insertion] Match (cust10, veh12)
[2018-06-13 00:28:33][greedy_insertion] Match (cust11, veh12)
[2018-06-13 00:28:33][greedy_insertion] Match (cust13, veh12)
[2018-06-13 00:28:33][greedy_insertion] Match (cust17, veh18)

Trip-vehicle matching (TVM) pseudocode

Alonso-Mora et al 2017 PNAS 114(3): pp.462-467, 2017

Input: R = {r1, ..., rn}; V = {v1, ..., vn}
Output: Assignments = {(ri, vj) : ri and vj are matched together}

BEGIN
for i in R:
    for j in R:
    
END

Negative solution cost for rs-lg-1

Cannot be reproduced consistently. For now compute the cost by parsing the dat file.

TODO Doc: Getting Started

it doesnt direct to the website to start the setup

time window constraints on new routes are not checked properly

check_timewindow_constr is executed on a route that does not include the vehicle's already traveled distance. this distance gets added later, during commit(), but should be added before check_timewindow_constr.

Create small problem instance for testing

Create a small problem instance for testing. The problem instance will be "synthetic-random" type. The input will be the Chengdu road network, bounded by the first ring (aka CD1). The problem set will have 5 vehicles and 10 customers. The format for the problem set will be:

cd1-SR-n10m5-x
VEHICLES 5
CUSTOMERS 10
<blank line>
ID    ORIGIN    DEST    Q    EARLY    LATE
1    518    830    1    0    189
...

Explanation:
Line 1: problem instance name
Line 2: "VEHICLES n" where n = number of vehicles in the instance
Line 3: "CUSTOMERS m" where m = number of customers in the instance
Line 4: blank
Line 5: column headers, tab delimited
Lines 6 -- (n+m+5): the customer or vehicle.

Columns (tab-delimited):
ID is vehicle/customer ID, starting from 1
ORIGIN is the ID of a node in the road network
DEST is the ID of a node in the road network
Q is the demand/capacity; positive=customer demand, negative=vehicle capacity
EARLY is the earliest departure time, equals the time the veh/cust appears online
LATE is the latest arrival time

Procedure to generate the instance:

Partition the road network into a grid (determine how many cells to use)
Select a random node in a random cell to be the origin; repeat to select the destination; do this (n+m) times
Randomly select n of the pairs obtained in Step 2 to be vehicles, and m to be customers
Set all vehicle capacities (Q) to be -2
Set all customer capacities to be +1
For time windows, randomly set EARLY to be between 0--300 (so they all come online within the first 5 minutes)
For LATE, calculate the travel distance between origin-destination for each veh/cust, convert it to a time using the constant speed 10 meters/second, then add a random number between 300--600 (so, a trip delay between 5 and 10 minutes)

The .cc files are not in www/public/example

Could you please add .cc files to the Cargo repository? Thank you

Cargo hangs after a while

I tried running cargo::start() on rs-lg-5 without giving it any algorithm and observed it hanged my computer. The first time I was unable to ctrl+c to kill it, I could only hard-restart my computer. The second time ctrl+c worked fine. The first hang occurred around t=1700, the second hang occurred at t=4120.

Bilateral Arrangement (BA) pseudocode

Cheng et al SIGMOD, 2017 pp.1197-1210

Bilateral Arrangement
Given a customer, try to assign it to a vehicle

bilateral_arrangement(customer) {
    vehicles = get_candidates(customer)
    while vehicles is not empty: # O(m)
        best_cost = inf
        best_vehicle = null
        best_sch = null
        for each vehicle in vehicles: # O(m)
            (cost, route, sch) # do not check constraints
                = sop_insertion_unsafe(vehicle.schedule, customer) # O(n^2)
            if cost < best_cost:
                best_cost = cost
                best_vehicle = vehicle
                best_sch = sch
        vehicle = vehicles.extract(best_vehicle)
        best_sch.owner = vehicle
        if check_precedence_constr(best_sch) and
            check_timewindow_constr(best_sch):
            return (best_cost, best_route, best_sch)
        else:
            randomly remove customer x from best_sch
            (cost, route, sch)
                = sop_insertion_unsafe(best_sch, customer)
            if check_precedence_constr(best_sch) and
                check_timewindow_constr(best_sch):
                add customer x back to the queue
                # best_sch no longer contains x
                return (best_cost, best_route, best_sch)
}

cargo::start() crashing due to map out of range

Different from issue #15 ... this one is due to map access. Example, running cargo::start() (no algorithm) on rs-lg-5:

[2018-06-15 22:10:06][cargo] t=9432; stepped 1 vehicles; remaining=0;
[2018-06-15 22:10:07][cargo] Finished algorithm noname
[Thread 0x7ffff5d79700 (LWP 6820) exited]
[2018-06-15 22:10:07][cargo] Writing solution...
terminate called after throwing an instance of 'std::out_of_range'
  what():  _Map_base::at

Thread 1 "greedy_insertio" received signal SIGABRT, Aborted.

Notice the simulation has already finished. The error is throw during writing solution.

Sum of "rejected" and "matched" in solution file adds up to more than number of customers

The cause seems to be "rejected" gets counted multiple times if the same customer is rejected multiple times

customer can be picked up twice

select_waiting_customers returns customers that may have already been assigned, but not yet picked up (status = waiting). A user's RSAlgorithm can assign such a customer to a new vehicle. But the previous assignment vehicle never gets corrected. This vehicle will still follow a route as if picking up the customer, and its schedule will still have the customer's pickup and dropoffs.

The potential fix is complicated.

If the vehicle is already enroute to the customer, then what to do? Remove the customer stops and re-route the vehicle?
If disallow re-assignment, then some algorithms may be unable to be implemented?

Solutions pseudocode

We will implement two greedy-based methods, one grouping method, and two iterative optimization methods. The classifications according to the paper:

Exact - trip-vehicle grouping (Alonso-Mora 2017)
Approx - hybrid simulated annealing (Jung 2016)
Data-driven - (1) insertion (Ma 2015), (2) kinetic tree (Huang 2014), (3) bilateral arrangement (Cheng 2017)
Baseline - nearest-neighbor (found in Jung 2016)

Pseudocodes

Assume the simulator supplies batches of requests R. The batch can be either by time (e.g. collect requests into R every 30 seconds) or by number (e.g. R can be size 1). When a new batch arrives, one of the following methods is executed. The goal of the method is to assign the requests in R to vehicles.
The output of each method is a set of assignments. An assignment is a pair of ID's (request ID, vehicle ID). If a request ID is in R but not in the assignments, then it was unmatched.

Input: set of customer requests R
Output: set of assignments A

Nearest Neighbor

NEAREST_NEIGHBOR
increment = 10
for each req in R:
    base = 0
    match_id = -1
    while match_id is -1 and base <= number_of_vehicles:
        k = (base + increment)
        candidates = knn(road_net, k, req.origin)
        for i from base to (k-1):
            S = candidates[i].schedule
            T = schedule_insertion_add(S, req.origin, req.destination)





NearestNeighbor::assign(queue reqs, queue replay) {
    while reqs not empty {
        req = dequeue(reqs)
        vehs = rnet.knn(req.origin, k=# of vehicles)
        cost = -1
        match_id = -1;
        for each v in vehs {
            sch = schm.at(v.id)
            cost = LowestCost(sch, req, sch_out)
            if (cost) {
                match_id = v.id
                break
            }
        }
        if (match_id == -1) add req to replay
        else add (req.id, v.id, sch_out) to ResultsSet
    }
    return ResultsSet        
}

Insertion approach (based on TShare)

Given a request req

min_cost = inf
match_id = -1
V = set of valid candidates
for each vehicle in V:
    for each position in the vehicle's schedule:
        insert req.pickup
        if schedule meets constraints:
            for each remaining position in the schedule:
                insert req.destination
                if schedule meets constraints:
                    if the cost of the schedule < min_cost
                        set min_cost = this cost
                        set match_id = vehicle's id
if match_id != -1
    update the schedule for match_id
    return the assignment (match_id, request_id)

Kinetic-tree approach (based on Noah)

min_cost = inf
match_id = -1
V = set of valid candidates
create a node PICK for req.pickup
create a node DROP for req.dropoff
for each vehicle in V:
    retrieve the vehicle's kinetic tree, KT
    for each valid node while traversing KT:
        update KT = insertNode(node, PICK)
    min_branch_cost = branch of KT with lowest cost
    if min_branch_cost < min_cost:
        update min_cost to be this cost
        set match_id = vehicle's id
if match_id != -1
    update the schedule for match_id
    return the assignment (match_id, request_id)

function insertNode(node* HEAD, node N) {
    copy HEAD.children into N.children
    move N to be a child of HEAD
    prune infeasible branches in the HEAD -> N -> .. subtree
    insertNode(N, DROP)
    for each child of HEAD not N:
        insertNode(child, N)
    return HEAD
}

Note1: a "valid node" while traversing KT is when the distance from the vehicle's
current location to the node to be inserted is within constraints; this saves us
from traversing the whole tree

Note2: maybe a non-recursive version can be easier to implement/debug

Note3: a map can be used instead of a tree (I think the operations (copy, insert)
will have the same performance properties, so no difference? just the map needs
more memory)

The methods Insertion and KineticTree need to get the valid vehicles first. This can be done using a simple grid index, here is the pseudo-code:

Get valid vehicles

Given a request req

d = shortest_path(req.origin, req.destination)
duration = d/(vehicle speed)
threshold = (req.late - req.early) - duration
radius = threshold*(vehicle speed)
return all vehicles in all cells within radius of req.origin

Trip Grouping based on RV/RTV graph

Incomplete

Given a batch of requests R, all vehicles V

# Build RV graph
set RV to be an empty graph
for each pair (r1, r2) in R cross-join R:
    if
        schedule (r1.origin, r2.origin, r1.destination, r2.destination) or
        schedule (r1.origin, r2.origin, r2.destination, r1.destination) or
        schedule (r2.origin, r1.origin, r2.destination, r1.destination) or
        schedule (r2.origin, r1.origin, r1.destination, r2.destination) is valid:
        add r1, r2 as nodes in RV
        add edge (r1, r2) with weight as the cost of the valid schedule
for each pair (vehicle, req) in V cross-join R:
    try to schedule req into vehicle's schedule (using insertion-approach,
        exhaustive search, ...)
    if there is a valid schedule:
        add vehicle, req as nodes in RV
        add edge (vehicle, req) with weight as the cost of the valid schedule

# Build RTV graph
for each vehicle in V:
    for

Prepare query failed: what(): out of memory

Prepare query failed:
select route, idx_last_visited_node, next_node_distance from vehicles where  id = ?
terminate called after throwing an instance of 'std::runtime_error'
  what():  out of memory
Aborted (core dumped)

Reason:

An RSAlgorithm class is initialized before a Cargo class. The RSAlgorithm class tries to prepare statements against the Cargo DB, but the DB is not created yet. sqlite3_errmsg in dbsql.cc > prepare_stmt(2) receives a bad pointer, hence we get a misleading error message (see https://stackoverflow.com/questions/43321649/failed-from-sqlite3-prepare-v2-error-is-out-of-memory).

Workaround:

Initialize Cargo before RSAlgorithm. For example:

/* BAD */
MyAlg A;  // extends RSAlgorithm
Cargo(options);

/* GOOD */
Cargo(options);
MyAlg A;

low performance in greedy insertion

At t=1236 on rs-lg-5, greedy insertion takes nearly 1 minute to complete one listen()->handle_vehicle->handle_customer cycle!!!

[2018-06-17 14:13:08][greedy_insertion] listen() (56157 ms) exceeds batch time (1000 ms)

This is causing major inaccuracies because when vehicles get matched after such a long cycle time, they are rolled back to a way earlier state than they should be. Besides, greedy is supposed to be the fastest method! At this particular time step there are 222 active vehicles, not sure how many customers.

customer still gets handled, even after pickup

Veh12 pickups up cust13 at t=150, but at t=154 cust 13 still triggers handle_customer()

[2018-06-13 00:31:24][cargo] Vehicle 12 picked up Customer 13(3511)
[2018-06-13 00:31:24][cargo] t=150; stepped 5 vehicles; remaining=5;
...
[2018-06-13 00:31:24][cargo] t=154; stepped 5 vehicles; remaining=5;
[2018-06-13 00:31:24][greedy_insertion] Handling customer 13