Otto-von-Guericke-Universität Magdeburg


FEMM - Working Paper Series - 2017


Henriette Koch/Maximilian Schlögell/Andreas Bortfeldt
A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls

In this paper, a variant of the vehicle routing problem with mixed backhauls (VRPMB) is presented, i.e. goods have to be delivered from a central depot to linehaul customers, and, at the same time, goods have to be picked up from backhaul customers and brought to the depot. Both types of customers can be visited in mixed sequences.
The goods to be delivered or picked up are three-dimensional (cuboid) items. Hence, in addition to a routing plan, a feasible packing plan for each tour has to be provided considering a number of loading constraints. The resulting problem is the vehicle routing problem with three-dimensional loading constraints and mixed backhauls (3L-VRPMB).
The simultaneous transport of linehaul and backhaul items presents a particular challenge of the problem. We consider two different loading variants in order to avoid any reloading during the tour: (i) rear loading with separate linehaul and backhaul sections and (ii) loading at a long side.
In order to solve the problem, we propose a hybrid metaheuristic consisting of a reactive tabu search for the routing problem and different packing heuristics for the loading problem. Numerical experiments are reported with benchmark instances from the literature for the one-dimensional VRPMB to examine the performance of the routing algorithm and with newly generated instances for the 3L-VRPMB.

Keywords: vehicle routing, backhauls, tabu search, packing

Dirk Männel
Hybrid Algorithms for the Vehicle Routing Problem with Pickup and Delivery and Two-dimensional Loading Constraints

We extend the classical Pickup and Delivery Problem (PDP) to an integrated routing and two-dimensional loading problem, called PDP with two-dimensional loading constraints (2L-PDP). A set of routes of minimum total length has to be determined such that each request is transported from a loading site to the corresponding unloading site. Each request consists of a given set of 2D rectangular items with a certain weight. The vehicles have a weight capacity and a rectangular two-dimensional loading area. All loading and unloading operations must be done exclusively by movements parallel to the longitudinal axis of the loading area of a vehicle and without moving items of other requests. Furthermore, each item must not be moved after loading and before unloading.
The problem is of interest for the transport of rectangular-shaped items that cannot be stacked one on top of the other because of their weight, fragility or large dimensions. The 2L-PDP also generalizes the well-known Capacitated Vehicle Routing Problem with Two-dimensional Loading Constraints (2L-CVRP), in which the demand of each customer is to be transported from the depot to the customer’s unloading site.
This paper proposes two hybrid algorithms for solving the 2L-PDP and each one consists of a routing and a packing procedure. Within both approaches, the routing procedure modifies a well-known large neighborhood search for the one-dimensional PDP and the packing procedure uses six different constructive heuristics for packing the items. Computational experiments were carried out using 60 newly proposed 2L-PDP benchmark instances with up to 150 requests.

Keywords: Transportation, vehicle routing, packing, pickup and delivery

Michael Mitzkewitz
Equilibrium Selection and Simple Signaling Games

This paper calculates the Harsanyi-Selten solutions for a class of simple signaling games. This means that for each generic game belonging to this class one of its equilibrium points is selected according to the principles developed by John C. Harsanyi and Reinhard Selten (Harsanyi & Selten, A General Theory of Equilibrium Selection in Games, 1988). For almost fifty years signaling games have been of great interest for both normative game theorists and scientists in-terested in the analysis of social, cultural and biological phenomena. The paper provides an introduction into the Harsanyi-Selten theory, solves all generic games and subsumes the results. Thus comparisons to Nash refinement concepts can easily be done and the solution of more complex games is facilitated.

JEL: C72
Keywords: Noncooperative Game Theory, Signaling Games, Equilibrium Selec-tion, Harsanyi-Selten theory, Risk Dominance, Tracing Procedure

Alexander Erler/Horst Gischer/Bernhard Herz
Regional Competition in US Banking – Trends and Determinants

Competition in the US banking industry as measured by the Lerner Index has on average increased substantially during the last decade. At the same time, regional differences in competition on the state level have decreased considerably. Based on a dynamic panel framework we find that these developments are mainly driven by industry specific factors such as the costs to income ratio. The empirical evidence indicates that inefficiency and the Lerner index are significant negatively correlated. Macroeconomic conditions appear to have supported these trends in competition, however, to a somewhat lesser extent.

JEL: D40, G21, L19
Keywords: competition, US banking, efficiency, regional markets

Daniel Schubert/André Scholz/Gerhard Wäscher
Integrated Order Picking and Vehicle Routing with Due Dates

Supermarkets typically order their goods from a centrally located distribution center (warehouse). Each order that the warehouse receives is characterized by the requested items, the location of the respective supermarket and a due date by which the items have to be delivered. For processing an order, a human operator (order picker) retrieves the requested items from their storage locations in the warehouse first. The items are then available for shipment and loaded on the vehicle which performs the tour including the respective location of the supermarket. Whether and to which extent a due date is violated (tardiness) depends on the composition of the tours, the corresponding routes and the start dates of the tours (vehicle routing subproblem). The start date of a tour, however, is also affected by the assignment of orders to pickers and the sequence according to which the orders are processed by the pickers (order picking subproblem). Although both subproblems are closely interconnected, they have not been considered simultaneously in the literature so far. In this paper, an iterated local search algorithm is designed for the simultaneous solution of the subproblems. By means of extensive numerical experiments, it is shown that the proposed approach is able to generate high-quality solutions even for large instances. Furthermore, the economic benefits of an integrated solution are investigated. Problem classes are identified, where the sequential solution of the subproblems leads to acceptable results, and it is pointed out in which cases an integrated solution is inevitable.

Keywords: Vehicle Routing, Order Picking, Parallel Machine Scheduling, Iterated Local Search

Sandra Hahn/André Scholz
Order Picking in Narrow-Aisle Warehouses: A Fast Approach to Minimize Waiting Times
Abstract: Mail order companies like Zalando or Amazon reported a significant increase regarding the number of incoming customer orders in recent years. Customers are served from a central distribution center (warehouse) where requested items of the orders have to be retrieved (picked) from their storage locations. The picking process is performed by human operators (order pickers) who are employed on a large scale in order to enable a fast processing of the orders. However, due to limited space, aisles are often very narrow in warehouses, and order pickers cannot pass or overtake each other. Thus, an order picker may have to wait until another picker has performed his/her operations. The arising waiting times may significantly increase the processing times of the orders, implying that a large number of pickers does not guarantee for small processing times. Therefore, in this paper, the impact of several problem parameters on the amount of waiting time is investigated first and situations are identified where the consideration of waiting times is inevitable for an efficient organization of the picking process. In the second part of the paper, a solution approach, namely a truncated branch-and-bound algorithm, is proposed which aims for the minimization of the waiting times. By means of extensive numerical experiments, it is demonstrated that this approach provides high-quality solutions within a very small amount of computing time.
Keywords: Order Picking, Picker Routing, Picker Blocking

Henriette Koch/Andreas Bortfeldt/Gerhard Wäscher
A hybrid solution approach for the 3L-VRP with simultaneous delivery and pickups

This paper deals with a special vehicle routing problem with backhauls where each customer receives items from a depot and, at the same time, returns items back to the depot. Moreover, time windows are assumed and three-dimensional loading constraints are to be observed, i.e. the items are three-dimensional boxes and packing constraints, e.g. regarding load stability, are to be met. The resulting problem is the vehicle routing problem with simultaneous delivery and pickup (VRPSDP), time windows, and three-dimensional loading constraints (3L-VRPSDPTW). This problem occurs, for example, if retail stores are supplied by a central warehouse and wish to return packaging material.
A particular challenge of the problem is to transport delivery and pickup items simultaneously on the same vehicle. In order to avoid any reloading effort during a tour, we consider two different loading approaches of vehicles: (i) loading from the back side with separation of the loading space into a delivery section and a pickup section and (ii) loading at the long side.
A hybrid algorithm is proposed for the 3L-VRPSDPTW consisting of an adaptive large neighbourhood search for the routing and different packing heuristics for the loading part of the problem. Extensive numerical experiments are conducted with VRPSDP instances from the literature and newly generated instances for the 3LVRPSDPTW.


vehicle routing, backhauls, three-dimensional loading constraints, large neighbourhood search

Tino Henke/M. Grazia Speranza/Gerhard Wäscher
A Branch-and-Cut Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes

Multi-compartment vehicle routing problems arise in a variety of problem settings in which different product types have to be transported separated from each other. In this paper, a problem variant which occurs in the context of glass waste recycling is considered. In this problem, a set of locations exists, each of which offering a number of containers for the collection of different types of glass waste (e.g. colorless, green, brown glass). In order to pick up the contents from the containers, a fleet of homogeneous disposal vehicles is available. Individually for each disposal vehicle, the capacity can be discretely separated into a limited number of compartments to which different glass waste types are assigned. The objective of the problem is to minimize the total distance to be travelled by the disposal vehicles.
For solving this problem to optimality, a branch-and-cut algorithm has been developed and implemented. Extensive numerical experiments have been conducted in order to evaluate the algorithm and to gain insights into the problem structure. The corresponding results show that the algorithm is able to solve instances with up to 50 locations to optimality and that it reduces the computing time by 87% compared to instances from the literature. Additional experiments give managerial insights into the use of different variants of compartments with flexible sizes.

Keywords:  vehicle routing, multiple compartments, branch-and-cut algorithm, waste collection

Peter Reichling/Anastasiia Zbandut
Costs of capital under credit risk

Credit risk analysis represents a growing field in financial research since decades. However, in company valuation – to be more precise, in cost of capital computations – credit risk is merely taken into consideration at the level of the debt beta approach. Our paper proves that applications of the debt beta approach suffer from unrealistic assumptions. As an advantageous approach, we develop an alternative framework to determine costs of capital based on Merton’s model. We present (quasi-) analytic formulas for costs of equity and debt which are consistent with Modigliani-Miller theory in continuous-time and discrete-time settings without taxes. Our framework is superior to the debt beta approach regarding the quantity and quality of required data in peer group analysis. Since equity and debt are represented by options in Merton’s model, we compute expected option rates of return without resorting to betas. Thereby, our paper also contributes to the option pricing literature.

JEL:  G13, G32, G33
Keywords:  Company valuation, debt beta, expected option return, Merton’s model, WACC

Andreas Welling
Green Finance: Recent developments, characteristics and important actors

Various so-called green investments are intended to limit the warming of the earth's climate, thus minimizing social, environmental and economic damage. The article introduces into the corresponding research field of Green Finance by providing current data, by showing historical developments, and by forecasting future tasks. Further, the article depicts the major difficulties of research on Green Finance; particularly rapid technological progress, the dependence of governmental support, high uncertainties, and, especially the interactions of so many actors. Finally, the article gives a short review on the research field of Green Finance.


Andreas Welling
Optimal Carbon Tax Scheme under Uncertainty in an Oligopolistic Market of Polluters

Carbon taxation is used by several countries to internalize the negative effects of carbon emissions to the emitters of carbon. In this article the effects of a carbon tax on an oligopolistic market of polluters are analyzed. With the help of a multi-criteria optimization model the optimal carbon tax rate is determined; first under certainty and then in presence of demand uncertainty. It is shown that demand uncertainty leads to a lower optimal carbon tax rate, while it simultaneously increases carbon emissions. Finally, the influence of a possible carbon emission reducing investment is analyzed with the help of a real option model.

Keywords: Carbon Tax; Climate Change; Real Option; Technological Progress; Uncertainty; Oligopolistic competition

Letzte Änderung: 01.08.2017 - Ansprechpartner: Webmaster