Please enable JavaScript.
Coggle requires JavaScript to display documents.
Warehousing & Delivery Logistics - Coggle Diagram
Warehousing & Delivery Logistics
Chapter 1
Roles of warehousing:
Buffering
Consolidation
Value-added processing
Delivery logistics:
Definition
Challenges
Chapter 2:
Receiving and classical storage assignment
Planning problem in receiving
Staff planning
Buffer assignment
Task scheduling
Storage assignment:
Definition:
Decision of where to store incoming goods
Idea: Storage assignment is not time-critical processes --> use to speed up a time-critical process (order picking)
Storage assignment: 2 extremes
Random storage (RS)
: all products can be stored in any open storage position
Good space utilization
Minimal organizational overhead
Bad average length of picking tour
--> Only 1 class
Volume-based storage (VBM
): Each SKU gets assigned to a dedicated storage position (higher demand --> closer to the depot
Bad space utilization
High organizational overhead
Good average length of picking tour
--> Each SKU has its own class
Class-based storage: combines the best if both extreme strategies
SKUs are assigned based on customer demand (A-B-C class)
Within each storage area, random storage is applied
More classes are not always better --> space efficiency shrinks
Chapter 3:
Mixed-shelves storage assignment
Classical/store-based retailing
Online retailing
Mixed-shelves storage: Items of the same SKU are assigned to different storage positions, (1 storage position holds several SKUs)
Advantages: shorter picking tours
Pickers can hand over completely picked order to closet depot
an item of a demanded SKU is always close by
Scattered storage assignment problem (SSA)
Idea: minimize the maximum distance from measuring point
SSA-MIP: objective and 7 constraints
Chapter 4: Picker routing
Ratliff and Rosethal
Rectangular warehouse, 2 cross-aisles, 1 storage position per SKU, 1 depot in the middle of a cross-aisle
Travelling salesman problem (TSP)
TSP-MIP: Objective (minimize the total costs of all edges) and 5 constraints
TSP is in the class of np-hard problems
The solution time needed to find optimal solution grows exponentially with the size of problem instance
For n vertices (including the starting position) --> n! solution exist
Solving TSP in rectangular warehouse
Options to enter aisle: 6 options
Options to connect 2 aisles: 5 options
Incoming order with demand for SKUs
Each SKU translate into 1 storage position within the warehouse
All storage positions of demanded SKUs must be visited
The tour starts and ends at the depot
--> Travelling salesman problem (TSP)
Chapter 5:
Mixed-shelves storage picker routing
Incoming orders with demand for SKUs
Each SKU translates into a set of storage positions within the warehouse
For all demanded SKUs at least one storage position of the respective set must be visited
The tour starts and ends at the depot
-->
Picker routing problem in mixed shelves storage warehouses
Selection component: Select the most suited positions to visit per SKU
Routing component: plan a shortest tour between positions to visit
--> Ratliff and Rosenthal's idea cannot be used here, as it does not consider the selection component
Complexity of problems:
The time complexity of one algorithm depends on the length of input for a specific problem
P contains all problems which could be solved in polynomial time (depending on the length of problem input) by a deterministic Turing machine
NP contains all problems which could be solved in polynomial time by a non-deterministic Turing machine
A non-deterministic Turing machine is able to do the same as a deterministic Turing machine and maybe even more
Polynonmial-time reduction:
If you want to compare the difficulty of two problemsm you can use polynomial-time reduction
The basic idea is if you can easily translate an instance of problem A into an instance of problem B, B is at least as hard as A. Otherwise, you could translate the harder instance of problem A into an easier instance of problem B, solve it as an instance of B and retranslate it into a solution for problem A. if the translation is easy (in polynomial time), however, this is not possible
Satisfiability problem (SAT):
SAT is at least as hard as all problem in NP (NP-hard)
SAT is NP itself
SAT is among the hardest problems in NP (NP-complete)
You can use SAT as a basis to show that a problem cannot be solved in polynomial time by all existing algorithms (on a deterministic Turing machine) most probably
Picker routing problem
in a scattered storage warehouse is at least as hard as the hitting set problem, which is at last as hard as SAT
SAT is NP-hard --> picker routing problem in a scattered warehouse is NP-hard
If P # NP holds, there is no algorithm able to solve this problem in polynomial time on a deterministic Turing machine
Chapter 6:
Robotic mobile fulfillment
Picker-to-parts V.S Parts-to-picker
Mixed-shelves storage, items of the same SKU found on multiple racks and each rack holding items of multiple SKUs
Racks are lifted and transported by autonomously driving robots
Pickers within pick stations pick multiple orders in parallel
The mobile robot-based order picking problem for rack sequencing (MROP-RS)
Objective: Minimize the number of racks visited
11 constraints
An exact algorithm for MROP-RS:
*
Dynamic programming*:
A transition between 2 stages is only possible for consecutive stages/racks indices l and l+1 and each transition represents
adding a rack to the rack sequence, such that demands of currently processed orders are reduced and new orders (with maybe already reduced demand due to the currently visiting rack) can be added to the batch for each order completely picked
search for the earliest occurrence of final state representing all orders are picked.
Chapter 7:
Zoning, batching and sorting
Order batching
is the method of
grouping a set of orders into a number of subsets
, each of which can then be retrieved by a single picking tour
Time-window batching: Fixed time window batching V.S variable time window batching
Proximity batching
Sort-while-pick V.S sort-after-pick
Zoning
is the problem of
dividing the whole picking area into a number of smaller areas
and assigning order pickers to pick requested items within the zone
Synchronized/parallel zoning V.S progressive/sequential zoning
The batched order bin sequencing problem (BOBS)
Objective: minimize the total completion time of orders
6 constraints
Solving via an adapted shortest processing time (SPT) rule
For all not yet finished orders, computing remaining processing time
select an order with shortest remaining processing time
add all missing bins of the selected order to the sequence
repeat until all orders are finished
Dynamic programming approach:
The initial state is with cost 0
n+1 stages, starting from the last position
The cost of a transition are calculated by the completion time of the orders whose respective bins were not represented in the sequence until now and are determined by the newly assigned bin
Beam search (BS) and DP:
For each state, a lower bound (LB) can be computed, which represents an objective value, which will for sure not be undercut by any solution based on the considered partial solution
If the LB is greater or equal than the currently best known solution, the state does not need to be considered further
Chapter 8:
Cross docking
Initial leg --> main leg --> final leg --> last mile
planning problems: layout planning, destination assignment, truck scheduling, conveyor control
The truck scheduling problem in postal service industry (TSPS)
Objective: minimize the total weighted penalty of scheduling inbound trucks
7 constraints
iTSPS The interval scheduling version of the TSPS
Instead of allowing all possible starting times per truck, we let the model chose only among a limited number of options
Objective: minimize the total weighted penalty for assigning trucks to gate and processing intervals
3 constraints
k-COLORABILITY to iTSPS
Create a truck for each cluster and a processing interval of the truck for each vertex of the cluster
If an edge exists between 2 vertices, the processing intervals of the regarding trucks have to be selected such that they overlap. Otherwise, they must not overlap
The k colors are represented by k dock doors
Chapter 9:
Vehicle routing
The vehicle routing problem (VRP) - Minimizing the fleet size - An assignment-based formulation
Objective: Minimize the fleet size or vehicle
7 constraints
The vehicle routing problem - MInimizing the fleet size - A pattern-based formulation
Objective: minimizing the number of tours selected --> equivalently, minimizing the fleet size as each tour requires 1 vehicle
2 constraints
Column generation:
search for promising variables not considered yet
Reduced costs smaller than 0 --> variable should be added to the basis
Pricing model
Objective: find the route that minimizes the reduced cost, subject to feasibility constraints
8 constraints
Chapter 10:
Robot-based delivery
The truck-based robot delivery problem (TBRD)
Decomposition procedure for the TBRD:
Truck route: multi-start local search procedure
Launching plan of robot: classical transportation problem
Transportation problem:
Objective: Minimizing the cost of transporting all items from s to d