Vehicle Routing Functions - Category (Experimental)¶

Characteristics¶

• Capacitated Vehicle Routing Problem CVRP where The vehicles have limited carrying capacity of the goods.
• Vehicle Routing Problem with Time Windows VRPTW where the locations have time windows within which the vehicle’s visits must be made.
• Vehicle Routing Problem with Pickup and Delivery VRPPD where a number of goods need to be moved from certain pickup locations to other delivery locations.

Limitations

• No multiple time windows for a location.
• Less vehicle used is considered better.
• Less total duration is better.
• Less wait time is better.

Pick & deliver¶

Both implementations use the following same parameters:

The non euclidean implementation, additionally has:

Pick & Deliver Orders SQL¶

In general, the columns for the orders SQL is the same in both implementation of pick and delivery:

For the non euclidean implementation, the starting and ending identifiers are needed:

For the euclidean implementation, pick up and delivery \((x,y)\) locations are needed:

Pick & Deliver Vehicles SQL¶

In general, the columns for the vehicles_sql is the same in both implementation of pick and delivery:

For the non euclidean implementation, the starting and ending identifiers are needed:

For the euclidean implementation, starting and ending \((x,y)\) locations are needed:

Pick & Deliver Matrix SQL¶

Description of the result (TODO Disussion: Euclidean & Matrix)¶

RETURNS SET OF
    (seq, vehicle_seq, vehicle_id, stop_seq, stop_type,
        travel_time, arrival_time, wait_time, service_time,  departure_time)
    UNION
    (summary row)

Summary Row

Description of the result (TODO Disussion: Euclidean & Matrix)¶

RETURNS SET OF
    (seq, vehicle_seq, vehicle_id, stop_seq, stop_type,
        travel_time, arrival_time, wait_time, service_time,  departure_time)
    UNION
    (summary row)

Summary Row

Where:

Capacity and Demand Units Handling¶

The capacity of a vehicle, can be measured in:

• Volume units like \(m^3\).
• Area units like \(m^2\) (when no stacking is allowed).
• Weight units like \(kg\).
• Number of boxes that fit in the vehicle.
• Number of seats in the vehicle

The demand request of the pickup-deliver orders must use the same units as the units used in the vehicle’s capacity.

To handle problems like: 10 (equal dimension) boxes of apples and 5 kg of feathers that are to be transported (not packed in boxes).

If the vehicle’s capacity is measured by boxes, a conversion of kg of feathers to equivalent number of boxes is needed. If the vehicle’s capacity is measured by kg, a conversion of box of apples to equivalent number of kg is needed.

Showing how the 2 possible conversions can be done

Let: - \(f_boxes\): number of boxes that would be used for 1 kg of feathers. - \(a_weight\): weight of 1 box of apples.

Locations¶

• When using the Euclidean signatures:
  • The vehicles have \((x, y)\) pairs for start and ending locations.
  • The orders Have \((x, y)\) pairs for pickup and delivery locations.
• When using a matrix:
  • The vehicles have identifiers for the start and ending locations.
  • The orders have identifiers for the pickup and delivery locations.
  • All the identifiers are indices to the given matrix.

Time Handling¶

The times are relative to 0

Suppose that a vehicle’s driver starts the shift at 9:00 am and ends the shift at 4:30 pm and the service time duration is 10 minutes with 30 seconds.

All time units have to be converted

Factor Handling¶