The tour calculation consists of two successive phases. In the order collection, orders that can be fulfilled on a tour are collected together without the exact start or end time already being fixed. In the scheduling, a start time is defined for each tour in such a way that the number of required tugger train instances is minimized.

Order Collection

Input

A list L of transport orders for a route, sorted by earliest provision time

Route course with distances between waypoints for calculating driving times

The tugger configuration (tuggers with maximum speed, chaining factors)

Output

A list R of tours

Algorithm

• As long as L is not empty
• Create an empty Tour T
• Take first order A from L and add A to T
• If T violates capacity limits, shift plans or delivery time slots, note error condition for A
• For each order A in L
  • If A can be added to T without violating capacity limits, shift schedules or delivery time slots
  • Add A to T
  • Remove A from L
• Add T to R

Scheduling

Input

A list F of tours, with the earliest and latest possible start times, so that no shift plans or delivery slots are violated. F is sorted by earliest possible start time.

Output

One start time S_T for each tour T in F

One tugger instance R_T for each tour T in F

A list B of required tugger instances

Algorithm

• Initialize B to empty list
• For each tour T in F
• For each tugger instance R in B
  • If R is able to connect T seamlessly to another tour:
  • R_T = R
  • S_T = end time of the previous tour
  • Start new run of outer loop
• For each tugger instance R in B
• If R is able to connect T to another tour with a break:
  • R_T = R
  • S_T = Earliest possible start time of T
  • Start new run of outer loop
• Add new tugger instance R to B
• R_T = B
• S_T = Earliest possible start time of T