Create small problem instance for testing

[jamjpan]

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:

1. Partition the road network into a grid (determine how many cells to use)
2. Select a random node in a random cell to be the origin; repeat to select the destination; do this (n+m) times
3. Randomly select n of the pairs obtained in Step 2 to be vehicles, and m to be customers
4. Set all vehicle capacities (Q) to be -2
5. Set all customer capacities to be +1
6. For time windows, randomly set EARLY to be between 0--300 (so they all come online within the first 5 minutes)
7. 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)

[jamjpan]

The range for EARLY and the trip delay for LATE can be adjusted... to make a more interesting problem instance.. if necessary. Also the ORIGIN and DEST can be manually adjusted in case the procedure generates really long trips... But the procedure will be used to generate the real problem sets for the real experiments, so it may be handy to write a good code.

[Vancior]

Done. You can access the files via my cloud, in the public/dataset/ridesharing/chengdu. Guest account and password is guest/guest. I have given guests download permission. The code is quiet simple, even without any argument parser, just modify the TripGenerator constructor to get customized datasets in the EOF.

[Vancior]

No many features, need to be improved. As for the distances, maybe use a Gaussian distribution?

[jamjpan]

I reviewed the code, it looks fine. I also plotted the datasets you generated, they look great, thank you very much! No need for Gaussian here because the problem set is synthetic anyway, we don't have to try to make it very real (there will be another problem set for that).

[jamjpan]

Oh, one issue-- the late window is computed incorrectly. It should be time (in seconds) to travel from origin to dest using 10m/s as the vehicle speed, plus a random number between 300-600.

You will need to add edge weights to all the edges in the rnet file using Haversine formula, then use path finding like dijkstra to get the shortest path between origin/dest, convert the distance to seconds, then add the random number.

I can recommend NetworkX, it has path finding and is pretty easy to use.

Take your time, no hurry

[Vancior]

Fixed. Files on my cloud have been updated.

[jamjpan]

Nice job.

[jamjpan]

Note-- the column header 'VEH/CUST NO." is too long so I change it to ID in the final version. I also change the name to be something meaningful, cd1-SR-n10m5- to stand for "chengdu road network", "synthetic random", 5 vehicles, 10 customers