Keywords

1 Introduction

A few clicks, this is all it takes to get almost everything for our daily requirements. A banana from Ecuador or Australian wine, Amazon Fresh has everything available and, as members of Amazon Prime, we receive our orders within the next few hours. Naturally, the internet is not limited to exotic foodstuff, and customers are free to order everywhere, but it is a basic requirement of today’s commercial life that everything is available, at any time and everywhere. To achieve this, distribution centers mushroom all over the world, and trucks sneak along the street networks everywhere. In Germany, for instance, there are about 3 million registered trucks, which transported almost 79% of all goods and contributed 479 million tkm (tonne-kilometers) in 2017 [15]. Thus, efficient logistics processes have become the backbone of the modern society.

In this context, the paper on hand takes a look at a subdiscipline of logistics, which focuses on all logistics activities after the finished product leaves production until it is finally handed over to the customer. This subdiscipline is called outbound logistics, which is an umbrella term for a variety of processes, among which we focus on order picking (Sect. 2), transportation (Sect. 3), and the question of how to balance logistics workload in a fair manner (Sect. 4). The following sections summarize papers, which are part of the cumulative dissertation [10]. Given the limited space of this paper, however, we only roughly characterize the problems treated as well as the results gained and refer the interested reader to the respective papers for details.

2 Order Picking

The first part of the dissertation investigates order picking problems and is based on the papers [3, 11]. Order picking is the process of collecting products from an available assortment in a specified quantity defined by customer orders. In the era of e-commerce, warehouses face significant challenges, such as a huge amount of orders demanding small quantities, free shipping, and next-day (or even same-day) deliveries [2].

Thus, it is not surprising that there is a bulk of optimization problems in the area of order picking, such as layout design and warehouse location at the strategic level, as well as zoning, picker routing, order batching, and order sequencing at the operational level [5,6,7]. In this context, the first part of the thesis is devoted to two sequencing problems, which are highly operational planning tasks and thus demand fast solution procedures. While the papers both seek for a suited order sequence, they differ in their underlying storage system (A-Frame dispenser [3] vs. high-bay rack [11]) and thus their specific problem setting, resulting in different constraints and objectives. In general, however, they can (unanimously) be defined as follows. Given a set of orders \(\mathcal J=\{1,\ldots ,n\}\), we seek for an order sequence π, which is a permutation of set \(\mathcal J\) and a picking plan x(π) ∈ Ω minimizing the total picking costs F(x(π)) (caused by, e.g., picking time, wages, and picking errors):

$$\displaystyle \begin{aligned} \text{Minimize } & F(x(\pi)){} \end{aligned} $$
(1)
$$\displaystyle \begin{aligned} \text{s.t. } & x(\pi)\in\varOmega. && {} \end{aligned} $$
(2)

where Ω denotes the set of feasible solutions.

Within our investigations, it turned out that (1)–(2) is NP-hard for both problems [3, 11], so that determining an optimal solution for an increasing problem size may become difficult. However, the good news is that our complexity analysis further revealed that the remaining sub-problems are solvable in polynomial time when the order sequence π is given, i.e., the corresponding picking plan x(π) can efficiently be determined. Thus, we utilized this property to develop effective solution approaches. To obtain an initial solution, a straightforward greedy heuristic turned out as a promising approach determining good solutions within negligible computational time. More precisely, the procedure starts with an empty sequence and in each iteration, it appends the order increasing the objective value least. In this way, a first solution is generated as a starting point for further improvements due to tailor-made metaheuristics or exact algorithms. In [3], we propose a multi-start local search procedure using various neighborhoods to alter the sequence and improve the solution. The algorithm shows very effective within our computational study and robust against an increasing problem size, so that even instances of real-world size can be solved. In [11], a branch-and-bound procedure is introduced where each branch of the tree corresponds to a (partial) order sequence. With the developed solution techniques on hand, we further examine the gains of optimization. We compare the picking performance due to the optimized sequences and benchmark them with traditional first-come-first-serve sequences. Our results reveal a huge potential for improvement over the status quo.

More precisely, in [3], workers continuously refill the A-Frame dispenser. However, whenever the workforce is not able to timely replenish the SKUs, additional utility workers take over to guarantee an error-free order picking process. For the solutions obtained by our optimization approaches in only about 7% of all replenishment events a utility worker have to step in. Therefore, a reduction of 75% of the required utility workers can be achieved. On contrary, in [11], we showed that our tailor-made solution procedures decreased the overall order picking time up to 20% for a high-bay rack with crane-supplied pick face where pickers move along the pick face to collect all SKUs demanded.

3 Transportation

The second part of the dissertation examines transportation problems and is based on the papers [1, 12]. Broadly speaking, the general task of transportation is to transfer goods or people from A to B. What sounds so simple, is often actually a complex planning problem, especially when facing real-world requirements, such as free shipping and tight time windows. From a company’s point of view, transportation (and other logistics activities such as order picking) is a vital part of their supply chain, but not a value-adding one. Therefore, it is crucial to keep the costs low and plan wisely.

In the world of operations research, transportation of goods is most often associated with the well-known vehicle routing problem, and a vast amount of literature is available that considers a plethora of different problem settings. Given the current requirements of e-commerce, however, just-in-time (JIT) deliveries, i.e., the supply with goods at the point of time they are needed, are of particular interest. Thus, we focus on the JIT-concept in both papers [1, 12] and investigate a basic network structure of a single line where goods have to be transported from A to B.

In [12], the task is to find a feasible assignment of goods to tours and tours to trucks, such that each delivery is in time and the fleet size is minimized, i.e., we allow multiple subsequent tours of the trucks. Thus, we face with the problem to assemble truck deliveries and to schedule the trucks’ departure times at the same time. To solve this NP-hard problem, we develop an effective binary search method. The binary search approach is based on tight bounds on the optimal fleet size. Therefore, we identify relaxations that can be solved in polynomial time to obtain lower bounds. The upper bound is determined by dividing the problem into two subproblems, where the first one is solved by a polynomial time approximation scheme to determine the truckloads/tours at the first step. Afterward, at the second step, the procedure applies an optimal polynomial time approach to assign the loads/tours to trucks and to schedule the respective departure times (see [12]). Finally, we used our algorithms for a sensitivity analysis. It shows that the driving distance, the level of container standardization, and the time windows of the JIT-concept have a significant impact on the potential savings promised by optimized solutions [12].

In [1], we determine the trucks’ departure times for the example of truck platooning. A platoon describes a convoy of trucks that drive in close proximity after each other. The front truck controls the followers and due to the reduced gap in between them, the aerodynamic drag reduces and less fuel is consumed. Platooning is not only beneficial for economic reasons (e.g., lower fuel costs), but also for environmental ones (e.g., less pollution). In [1], the complexity status for different problem settings (cost functions, time windows, platoon lengths) is investigated. The presented polynomial time procedures provide a suited basis to tackle large-sized problems efficiently. Furthermore, the sensitivity analysis reveals that each of the investigated influencing factors (diffusion of platooning technology, willingness-to-wait, platoon length) strongly impacts the possible fuel savings and a careful planning is required to exploit the full potential of the platooning technology. In particular, our investigations showed that the possible amount of saved fuel might be considerably lower than the technical possible ones. This is indeed a critical result, as our single road problem setting supports the platooning concept, as finding (spatially and temporally) suited partners becomes increasingly unlikely for entire road networks. However, in light of technological developments such as autonomous driving, substantial savings (driver wages) can be achieved justifying the investment costs of truck platooning technology [1].

4 Workload Balancing

The last part of the dissertation examines balancing problems and is based on the papers [9, 13, 14]. Generally speaking, the purpose is to assign a set of tasks \(\mathcal J=\{1,\ldots ,n\}\), each defined by its workload p j (\(j\in \mathcal J\)), to a set of resources \(\mathcal I=\{1,\ldots ,m\}\) in order to obtain an even spread of workload. Let x ij = 1, if task \(j\in \mathcal J\) is assigned to resource \(i\in \mathcal I\) and x ij = 0 otherwise, then the problem can be defined as

$$\displaystyle \begin{aligned} \text{Minimize } & F(C_1,\ldots,C_m) {} \end{aligned} $$
(3)
$$\displaystyle \begin{aligned} \text{s.t. } &\sum_{j=1}^np_j x_{ij}= C_{i} &&i=1,\ldots,m{} \end{aligned} $$
(4)
$$\displaystyle \begin{aligned} &\sum_{i=1}^mx_{ij}=1 &&j=1,\ldots,n{} \end{aligned} $$
(5)
$$\displaystyle \begin{aligned} &x_{ij}\in \left\{0,1\right\}&&i=1,\ldots,m;\,j=1,\ldots,n{} \end{aligned} $$
(6)

where F represents different alternative (workload balancing) objectives, such as the makespan \(C_{\max }=\max _{i\in \mathcal I}C_i\), its counterpart \(C_{\min }=\min _{i\in \mathcal I}C_i\) (see [9]), the difference \(C_{\varDelta }= C_{\max }-C_{\min }\), or the sum of squared workloads \(C^2= \sum _{i\in \mathcal I}C_i^2\) (see [13, 14]). These problems are also known as machine scheduling problems and despite of their simple structure, they are mostly NP-hard.

Problems like (3)–(6) often occur as subproblems or relaxed problem versions. For instance, assume that there is a set of orders, which must be assembled in a warehouse. As a result of the picking problem, we obtain a set of picking tours \(\mathcal J\) with length p j (\(j\in \mathcal J\)), which must be assigned to the set of pickers \(\mathcal I\). One goal might be efficiency, so that we aim to minimize the total makespan for picking the given order set, i.e. \(C_{\max }\), or we seek for a fair share of work, i.e. C 2. Moreover, assume that there is a picking tour having to retrieve three washing machines, whereas during a second tour only a pair of socks has to be picked. Then, p j might represent the ergonomic stress of a picking tour \(j\in \mathcal J\) instead of its length and applying the objective C 2 yields an ergonomic distribution of work.

A major drawback of traditional objectives such as \(C_{\max }\), \(C_{\min }\), or C Δ is that they only take the boundaries into account. Thus, the workload of the remaining machines is only implicitly addressed and may even contravene the balancing issue. Thus, all machines must be considered explicitly, e.g., by C 2. Previous approaches tackled this problem with local search algorithms where the neighborhood is defined by interchanging jobs between pairs of machines. In the case of two machines, however, all the above objectives are equal and the procedure, thus, does not adequately target the general balancing objective. Therefore, we develop an effective solution method to optimally solve the three-machine case [13] and the m-machine case in general [14]. Moreover, we propose a suited local search algorithm to solve C 2 [13].

In [14], we further demonstrate that the developed exact and heuristic solution procedures can handle a vast amount of objectives (\(C_{\max }\), \(C_{\min }\), C Δ, and other related objectives). Furthermore, tests [13, 14] show a significant improvement compared to benchmark instances of [4, 8, 13] and the off-the-shelf solver Gurobi. The proposed algorithms do not only improve on the solution quality, but they were also capable to reduce the computation time by several orders of magnitude.

5 Conclusion

The thesis [10] is equally devoted to solving important practical problem settings and deriving theoretical findings for selected problems from the field of outbound logistics. We translate problems motivated from business practice into mathematical optimization problems and, based on their complexity status, develop suited solution procedures capable of handling large-sized instances within short response times. Thus, these algorithms can be applied for operational and tactical planning tasks, such as order sequencing in warehousing, the scheduling of truck deliveries, or workload balancing.

It can be concluded, that sophisticated optimization is a suitable tool to considerably improve over the simple rules-of-thumb that are usually applied in business practice. Technological developments are often merely a first step to gain competitive advantages but optimization deciding on an intelligent application of the technologies is almost always equally important. For instance, in our platooning example, test applications show that fuel savings up to 10% or even 15% are technologically possible. However, this requires that, at any time, a suited platooning partner is available. Therefore, sophisticated matching algorithms to form platoons are needed which constitutes a delightful task for optimization.