Centre National de la Recherche Scientifique Institut Polytechnique de Grenoble Université Joseph Fourier

Laboratoire G-SCOP46, av Félix Viallet38031 Grenoble Cedexwww.g-scop.fr

INTEGRATING TRUCK SCHEDULING

AND EMPLOYEE ROSTERING IN A

CROSS-DOCKING PLATFORM – AN

ITERATIVE APPROACHAnne-Laure Ladier, Gülgün Alpan

2

CROSS-DOCKING OPERATIONSLess than 24h

of temporary

storageDocking

Unloading

Control

Transfer

Loading

1 color = 1 client

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

GENERAL IDEA

3

How to schedule the trucks and employees together?

Van Belle et al. (2012)

Ladier et Alpan (2014)

Günther et Nissen (2014)

Ladier et al. (2014)

« The scheduling of the trucks heavily influences the

workload for the internal resources »

Van Belle et al. (2012)

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

CROSS-DOCK TRUCK SCHEDULING

Ladier et Alpan (2014)

5

TRUCK SCHEDULING PROBLEM

Reservation system

Minimize Quantity put in storage

Dissatisfaction of the transportation providers

10am-12am

6am-8am

9am-12am

6am-7am

6am-9am

6am-9am

11am-12am

7am-10am

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

6

DECISIONS VARIABLES

Number of units moving at each time period: from each inbound truck to each outbound truck

from each inbound truck to storage

from storage to each outbound truck

Time windows chosen for the trucks

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

INTEGER PROGRAMMING MODEL

(IP*)min ( a0 × penalty on the inbound time window chosen

+ b0 × penalty on the outbound time window chosen + g0 × number of pallets put in storage)

# trucks present ≤ # doors

Pallets move from the present trucks only

Flow conservation (for each destination)

Outbound truck leave when fully loaded

Each truck is assigned to exactly 1 time window

Stock conservation rule

7

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

EMPLOYEE ROSTERING

Ladier et al. (2014)

9

EMPLOYEE ROSTERING

Manpower: 1st cost center for logistic providers

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

10

SEQUENTIAL SOLVING

Detailed task

allocation

Starting/ending

time per

employees1 or 2

weeks

¼ hour

Weekly

tim

eta

blin

g

Daily

rost

eri

ng

Nb temporary

workers

Total nb hours

workedExact times

Day

Hour and shift

Ben works 8

hours on Friday

Ben works from

9h to 17h on

Friday

Ben unloads

from 9h to

11h15, controls

from 11h15 to

12h …

MILP1

MILP2

MILP3

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

INTEGRATED PROBLEM

How to solve both problems in an integrated manner?

11

12

SEQUENTIAL APPROACHIntuitive approach:

Manage external

matters first, then

internal

Input data

IP H2or

MILP1

MILP2MILP3

Workload Workload

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

13

ITERATIVE APPROACH: IDEAS

Aircraft routing and crew scheduling (Weide et al. 2010)

Crew scheduling

Aircraft routing

The objective function of

each module integrates

information from the problem

solved previously

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

Linking

constraints

ITERATIVE APPROACH:

PRINCIPLE

14

Workload

Capacity contraints

Employe

es

first

Trucks

first

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

15

EMPLOYEES FIRSTInput data

IP H2ou

MILP1

MILP2

MILP3

Workload

Capacity

constraints

Announced timetable

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

TRUCK FIRST

16

Input data

IP* H2or

MILP1

MILP2

MILP3

IP H2orWorkload

Capacity

constraints

Announced

timetable

WorkloadWorkload

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

17

RESULTS

Stock

Employees

Truck ponctuality

Linking constraints

0.0 20.0 40.0 60.0 80.0

Trucks-first Employees-first

Average value of the related objective function elements

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

18

CONCLUSION

IP H2

MILP

1MILP

2

MILP

3

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

19

PERSPECTIVES

Optimal solution for the integrated problem?

Þ Adapt an idea from Guyon et al. (2010) Integrated production scheduling and employee

timetabling

Logic-based Benders decomposition

Slave problem = maximum flow problem

Context

Truck scheduling

Integrated pb ConclusionEmpl rostering

Centre National de la Recherche Scientifique Institut Polytechnique de Grenoble Université Joseph Fourier

Laboratoire G-SCOP46, av Félix Viallet38031 Grenoble Cedexwww.g-scop.fr

THANK YOU FOR YOUR

ATTENTIONwww.anne-laure-ladier.fr

anne-laure.ladier@insa-lyon.fr

21

BIBLIOGRAPHY Günther, M., & Nissen, V. (2014). A comparison of three heuristics on a practical

case of sub-daily staff scheduling. Annals of Operations Research, 218(1), 201–

219.

Guyon, O., Lemaire, P., Pinson, É., & Rivreau, D. (2010). Cut generation for an

integrated employee timetabling and production scheduling problem. European

Journal of Operational Research, 201(2), 557–567. doi:10.1016/j.ejor.2009.03.013

Ladier, A.-L., Alpan, G., & Penz, B. (2014). Joint employee weekly timetabling and

daily rostering: A decision-support tool for a logistics platform. European Journal of

Operational Research, 234(1), 278–291.

Ladier, A.-L., & Alpan, G. (2014). Crossdock truck scheduling with time windows −

Earliness, tardiness and storage policies. Journal of Intelligent Manufacturing.

doi:10.1007/s10845-014-1014-4

Van Belle, J., Valckenaers, P., & Cattrysse, D. (2012). Cross-docking: State of the

art. Omega, 40(6), 827–846.

Weide, O., Ryan, D., & Ehrgott, M. (2010). An iterative approach to robust and

integrated aircraft routing and crew scheduling. Computers & Operations

Research, 37(5), 833–844.