3.12 Extension 11: Order Precedences

Download Workbook: pdp_extension_11.xlsx.

Opturion Freight has won a new contract that requires orders to be picked up from a factory in Albury via line haul, cross-docked at their depot and then delivered to customers in metropolitan Melbourne. Cross-docked orders take at least one hour to process at the depot.

To handle this, we treat each stage of a cross-docked order as a separate order within the optimiser. Here, we will have:

  1. Stage 1: Albury → Depot.
  2. Stage 2: Depot → Customer.

We need to ensure the following:

  1. Stage 1 must be completed before stage 2 begins.
  2. There is at least one hour between the delivery of stage 1 to the depot and the pickup of stage 2.
  3. Stage 2 can only be assigned to a vehicle if stage 1 has also been assigned to a vehicle.

Figure 13 illustrates the handling of each cross-docked order.

PIC

Figure 13: Cross-docking with order precedences.

We use order precedence relationships to do this. An order precedence relationship is a pair of orders, together with an optional duration called the gap. We call the orders in the pair before and after. The optimiser schedules the delivery of before so that it will be completed prior to the pickup of after. The gap is the minimum amount of time that must elapse between the completion of the delivery of before and the pickup of after. The optimiser will only generate solutions where both orders are assigned, or where both orders are not assigned. You cannot have a solution where, for example, after is assigned but before is not.

In the accompanying workbook, we have added a sheet named Order Precedences. This sheet lets you define order precedence relationships. It has three columns: the Before and After columns contain the identifiers of the orders in the precedence relationship and the Gap column specifies the duration of the gap. Here, we set the gap to 1:00 because at least one hour must elapse between the completion of the delivery of before and the pickup of after.

Table 23 shows the delivery completion times for the “Stage 1” orders, the pickup times for the “Stage 2” orders and the resulting gap. You can see that the pickup of every “Stage 2” order commences at least one hour after the completion of the delivery of the corresponding “Stage 1” order.

Order Stage 1 Delivery Completion Stage 2 Pickup Gap
Order1 09:57 11:27 01:30
Order2 10:02 13:22 03:20
Order3 10:07 13:22 03:15
Order4 10:32 13:22 02:50
Order5 10:17 11:27 01:10
Order6 10:27 11:27 01:00
Order7 10:22 11:27 01:05
Order8 10:12 11:27 01:15
Order9 10:37 13:22 02:45
Order10 10:42 13:22 02:40
Table 23: Solution precedence gaps.