Solutions pseudocode

[jamjpan]

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 

[Vancior]

class RoadNetwork
{
public:
    RoadNetwork(std::vector<node_t>, std::vector<edge_t>);
}

class TshareRN : public RoadNetwork
{
public:
    TshareRN(std::vector<node_t>, std::vector<edge_t>);
}

TshareRN::TshareRN(std::vector<node_t> ns, std::vector<edge_t> es)
: RoadNetwork(ns, es) {
    // build a grid network
}

[Vancior]

I was thinking how we can make the simulator more like a simulator. In the object tracking challenges, the benchmark just care about the output of each frame given the previous frames. Although our benchmark simulator is more comlicated than this, there might still be a way to focus on input and output.

Like we can have a run function without any parameter for the solution class, and user shall invoke a function in the beginning of run(), like int got = cargo.GetRequest(int n, std::queue<Request>& rq) to get n requests(for streaming requests is 1), and the simulator will store the number n and the get time t1. When the assignment task finishes, invoke cargo.AddAssignment(std::pair) or cargo.AddAssignments(std::vector<std::pair>), then the simulator will record time t2 and display the running time (t2-t1)/n.

[jamjpan]

Can it support simultaneous requests/assignments/maintenance?

---

From: Juntao Hu notifications@github.com Sent: Thursday, April 5, 2018 11:18 AM To: jamjpan/Cargo Cc: James Pan; Author Subject: Re: [jamjpan/Cargo] Solutions pseudocode (#1)

I was thinking how we can make the simulator more like a simulator. In the object tracking challenges, the benchmark just care about the output of each frame given the previous frames. Although our benchmark simulator is more comlicated than this, there might still be a way to focus on input and output.

Like we can have a run function without any parameter for the solution class, and user shall invoke a function in the beginning of run(), like int got = cargo.GetRequest(int n, std::queue& rq) to get n requests(for streaming requests is 1), and the simulator will store the number n and the get time t1. When the assignment task finishes, invoke cargo.AddAssignment(std::pair) or cargo.AddAssignments(std::vector), then the simulator will record time t2 and display the running time (t2-t1)/n.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHubhttps://github.com/jamjpan/Cargo/issues/1#issuecomment-378808948, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AFJWfczSBZWz7cGX_NaZ8Le8Y1Wbmfzvks5tlYzzgaJpZM4TFFY3.

[jamjpan]

@Vancior Hold off on implementing the TShare grid... experimentally it's not much better than a simple grid, and it has much higher maintenance cost. I want to discuss with Prof Li first.

[Vancior]

Sorry to reply late, I was working on my computer vision project. In my inital idea, requests and assignments are in the processor thread as we designed before, and the function caller is the solution, while maintenance is in the server thread, but the caller is the server. Maybe the index in TShare is updated too frequent. The paper says there will be a new status when joining in the ridesharing service, or when a passenger gets on or off the taxi, or at a frequency (e.g., every 20 seconds) while connected to the service.

[jamjpan]

No problem, you can prioritize your own work, haha. I am happy to have any help you can spare. I am back from Changzhou. I thought I would have time to work a little bit but.. I didn't. I saw many relatives and was very busy. I will work on the pseudocodes today and work on generating a problem set.

OK, assignments in the processor thread, that is ok. But I think maintenance should not be in the server thread. The key is the maintenance will take away time for a solution to do processing. For example, in one second, Solution A can do maintenance in 500 ms, then only has 500 ms to do processing; but Solution B can do maintenance in 150 ms, then has 850 ms to do processing, so maybe can match more requests.

I will send Dr Li his thoughts about if we need the TShare grid index. I think not necessary, because the computational difficult part is the scheduling, not the candidate-finding. TShare uses a O(n^2) scheduling-- it fixes the positions of the existing stops, then tries to insert the pickup, then tries to insert the destination. The naive method of testing every scheduling permutation is in O(n!), so the TShare method is a big improvement.

The index is updated every time the taxi sends a new GPS coordinate. You can see the paper in Sec 4.1: "If taxis are tracked, when new GPS records are received from taxis, taxi lists need to be updated." But you are also correct, the frequency can be reduced to only the few events based on Sec 3.. So I am not sure... what happens if taxis are not tracked?? Is the index not as accurate?

---

From: Juntao Hu notifications@github.com Sent: Sunday, April 8, 2018 10:41 AM To: jamjpan/Cargo Cc: James Pan; Author Subject: Re: [jamjpan/Cargo] Solutions pseudocode (#1)

Sorry to reply late, I was working on my computer vision project. In my inital idea, requests and assignments are in the processor thread as we designed before, and the function caller is the solution, while maintenance is in the server thread, but the caller is the server. Maybe the index in TShare is updated too frequent. The paper says there will be a new status when joining in the ridesharing service, or when a passenger gets on or off the taxi, or at a frequency (e.g., every 20 seconds) while connected to the service.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHubhttps://github.com/jamjpan/Cargo/issues/1#issuecomment-379514791, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AFJWfepwHAT7Vhso-TwVm_VvPOkNHrwDks5tmXi-gaJpZM4TFFY3.

[Vancior]

I'm trying to build a ground truth simulator from scratch, which doesn't have any relationship with the algorithms and could provide some interfaces. As for the maintanence time, I think in real-world scenario, matching and status updating are seperated, even in two different departments, so I treat it as a time-cost in another thread.

[jamjpan]

How about this? Good idea?

The below are different ways to insert an o-d pair into an existing vehicle schedule.
The methods are guaranteed to find only valid schedules
(meet the time window and capacity constraints).

function schedule_insertion_add(Vehicle veh, Request req, Schedule T):
    # Insert the o-d pair using the Insertion Heuristic to make new schedule T
    # Horn 2002, Ma 2015, Jung 2016
    # Returns the cost of T

function schedule_random_add(Vehicle veh, Request req, Schedule T):
    # Insert the o-d pair using a random-search strategy to make new schedule T
    # Returns the cost of T

function schedule_exhaustive_add(Vehicle veh, Request req, Schedule T):
    # Insert the o-d pair using an exhaustive search strategy to make new schedule T
    # Finds the least-cost schedule
    # Returns the cost of T

function schedule_kinetictree_add(Vehicle veh, Request req, Schedule T):
    # Insert the o-d pair by traversing a kinetic tree to make new schedule T
    # Huang 2014
    # Returns the cost of T

function cost(Schedule S, Route w):
    # Finds the shortest-path route w through S
    # Returns the cost of w