Testing Methodology

Core Tests

The functions Cargo::step() and RSAlgorithm::commit() are the core functions of the Cargo library. The first simulates the movement of the vehicles around the road network. The second assigns to the vehicles new schedules and routes.

Cargo::step()

Function int Cargo::step(int& ndeact) returns the number of vehicles stepped, and outputs the number of deactivated vehicles after the step into ndeact. The function is expected to have the following behavior:

• "moves" vehicles a distance based on `Options.vehicle_speed'
• if the movement causes the vehicle to be at (or past) its destination, deactivate the vehicle
• if the movement causes the vehicle to be at (or past) one or more stops, do:
  • for each pickup, increase the vehicle's load by one; set the picked up customer status to Enroute
  • for each dropoff, decrease the load by one; set the customer status to Arrived
  • remove each stop from the vehicle's schedule

To test for correctness, we design a test scenario, call step() multiple times, and compare the result of the call against known expectations. The test scenario is as follows:

• The "road network" is a single line with five points. The points are labeled 0, 1, 2, 3, 4, 5 in order. The distances (in parentheses) are: 0 (2) 1 (2) 2 (2) 3 (2) 4 (3) 5. The total length of the line is 11 units.
• One vehicle and three customers are on the road. Their origin/destinations are:
  • Vehicle: orig=0, dest=5
  • Customer1: orig=1, dest=3
  • Customer2: orig=2, dest=4
• The vehicle's schedule is (node|type): (0|VehlOrig) (1|CustOrig) (2|CustOrig) (3|CustDest) (4|CustDest) (5|VehlDest).
• Three vehicle speeds will be tested: 3, 11, and 12. These speeds are enough to test the following cases:
  • Moving past a stop
  • Moving past multiple stops
  • Moving exactly to a stop
  • Moving past the vehicle's destination
  • Moving exact to the vehicle's destination
  • Moving immediately to the vehicle's destination
  • Moving immediately past the vehicle's destination

The expectations: (Legend: lvn is "last-visited node"; nnd is "next-node distance")

#step()	Speed=3	Speed=11	Speed=12
1	lvn=1, nnd=1, Cust1(p)	Veh deact, all custs done	Veh deact, all custs done
2	lvn=3, nnd=2, Cust1(d), C2(p)	-	-
3	lvn=4, nnd=2, all custs done	-	-
4	lvn=5, nnd=-1, Veh deact	-	-

RSAlgorithm::assign()

Function assign() performs:

• Assign customers to a vehicle
• Remove previously assigned customers from a vehicle
• Update vehicle's route and schedule based on assignment change

Due to match latency, assign can be "strict" or non-strict. The concept of "prefix" determines the outcome of strict or non-strict assign. A route prefix is the sequence of waypoints already traveled by the vehicle.

• In strict assign, if the prefix of the updated route does not match what the vehicle has actually traveled, then reject the commit.
• In non-strict assign, if the prefix does not match, then re-route the vehicle using the updated vehicle information.

Function assign() will try to synchronize the updated route (schedule) with the vehicle's current route (schedule). When assign() is called, there are four movement possibilities:

1. Vehicle is at waypoint moving toward another waypoint
2. Vehicle is at waypoint moving toward a stop
3. Vehicle is at stop moving toward a waypoint
4. Vehicle is at stop moving toward another stop

The tests are based on these cases, using the same road network & vehicle speed as in the step() test.

Case 1: Waypoint ~> Waypoint

After 1 step, vehicle is at 1 moving to 2 with 1 unit of distance remaining.

Strict assign

• Fail: new schedule is 0, 1, 3, 5 (fails because vehicle has already passed 1)
• Pass: new schedule is 0, 2, 4, 5 (synced schedule is 2, 2, 4, 5)

Non-strict assign

new schedule is 0, 1, 3, 5, causing re-route schedule to be 2, 2, 1, 3, 5

• Fail: re-route route exceeds time window constraint
• Pass: re-route route passes time window constraint

Case 2: Waypoint ~> Stop

After 0 steps, vehicle is at 0 moving to 1 with 2 unit of distance remaining, following schedule 1, 1, 3, 5

Strict assign

• Fail: new schedule is 0, 0, 1, 2, 3, 5 (fails because vehicle has already passed 0)
• Pass: new schedule is 0, 1, 2, 3, 4, 5 (synced schedule is 1, 1, 2, 3, 4, 5)

Non-strict assign

new schedule is 0, 0, 1, 2, 3, 5, causing re-route schedule to be 1, 1, 0, 2, 3, 5 Fail: re-route exceeds time window Pass: re-route passes time window

Case 3: Stop ~> Waypoint

After 2 steps, vehicle is at 3 moving toward 4 with 2 unit of distance remaining, following schedule 4, 5

Strict assign

• Fail: new schedule is 0, 1, 2, 3, 4, 5 (vehicle has already passed 2)
• Pass: new schedule is 0, 1, 3, 4, 5 (synced schedule is 4, 4, 5, 5)

Non-strict assign

new schedule is 0, 1, 2, 3, 4, 5, causing re-route schedule to be 4, 2, 4, 5, 5 Fail: re-route exceeds time window Pass: re-route passes time window

Case 4: Stop ~> Stop

Set vehicle speed = 2; after 1 step, vehicle is at 1 moving toward 2 with 2 unit of distance remaining, following schedule 2, 2, 3, 4, 5

Strict assign

• Fail: new schedule is 0, 1, 1, 2, 3, 3, 4, 5 (vehicle already passed 1)
• Pass: new schedule is 0, 1, 2, 2, 3, 4, 4, 5 (synced schedule is 2, 2, 2, 3, 4, 4, 5)

Non-strict assign

new schedule is 0, 1, 1, 2, 3, 3, 4, 5, causing re-route schedule to be 2, 2, 1, 3, 3, 4, 5

• Fail: re-route exceeds time window
• Pass: re-route passes time window