Project 1: One Way Rental

Several automobile companies service a geographic region modeled as a planar graph. Nodes are cities/towns with rental facilities, and edges are two-way highway links between towns.

Cars are ``owned'' by local agents. One-way rentals cause a problem for the agencies because cars end up at remote locations. While rental companies often do rent out non-local cars, they prefer to keep cars local to make administration/licensing/service of the vehicles simpler, as well as to balance the distribution of vehicles in proportion to local needs.

To relocate non-local cars, rental companies employ drivers who we'll call ``relocators.'' A driver can relocate a car by driving it from one node to another via a highway. To simplify the problem, we'll assume that a driver can traverse a single edge in a day. Relocating a car to a distant location may take several days. Once a driver arrives at a new location, she can switch cars and continue relocating other cars.

In the event that a relocator arrives in a town that has no non-local cars to relocate, the relocator has a problem: How will she get to the next town? The answer is that multiple relocators (up to 4) can share a single vehicle. So a second relocator could pick up the first one in passing. Alternatively, two relocators could coordinate to enter the town in two vehicles and to leave in one vehicle. Other variations on this theme are possible.

Your first challenge is to figure out good scheduling strategies given a fixed budget d of relocators, and an initial layout of vehicles and relocators. Given a fixed time interval t (maybe several weeks), how many vehicles can be successfully relocated? Note that there is no payoff for getting a vehicle close to the destination; it must arrive at its home location to be counted.

At some point, the various rental companies in the region realized that they could do even better if they helped each other out. Each company operates on the same graph, but has a different layout of vehicles and relocators known only to them. Nevertherless, if company A offered company B's relocator a ride, then company B might repay the favor later, benefiting both companies. Note that every car must be driven by its owner's relocator -- only passengers may be from another company.

So, the companies organized a clearinghouse in which relocators could post ride-offers and requests-to-ride for various points in the future. The clearinghouse (a role played by the simulator here) will match up the two kinds of requests and communicate the outcome to both parties. Note that the simulator will not enforce the contract, so that either party might change their mind, or simply not show up at the appointed place and time. (It is probably inadvisable to renege too often, as the other party might bear a grudge.)

The precise format of offers and requests will be specified later. It will be possible to submit multiple offers/requests, and to withdraw offers/requests as others are accepted (to avoid double-booking).

We will run tournaments for both the single-company and multiple-company variants of the problem.

Some things to think about:

Ken Ross 2012-09-17