Optimization of Order Picking and Transportation in E-commerce

Abstract

Order picking and transportation are two important factors impacting the performance of E-Commerce. Therefore, this thesis studies a serious of optimization problems of order picking and transportation in E-Commerce.

Order picking, known as one of the most important activities in E-Commerce, is the process of picking products from their storage locations to meet customer demand. Order picking is estimated to represent as much as 60% of all labor activities in the warehouse. Therefore, it is a crucial component of the warehouse system. Order picking often occurs in automated storage and retrieval system (AS/RS). Since its introduction in the 1950s, many publications have paid attention to various issues of AS/RSs, including system configuration, travel time estimation, storage policies, dwell point strategies, request sequencing, and batching. The conventional AS/RS usually uses a storage/retrieval (S/R) machine to move the loads. Each S/R machine has a vertical drive, a horizontal drive, and one or two shuttle drives. Although the vertical and horizontal drives are able to simultaneously move for greater efficiency, they cannot handle overly heavy loads. Therefore, to apply AS/RSs to handle heavier loads, a new type of AS/RS, called the split-platform AS/RS (SP-AS/RS), was introduced and studied. In this thesis, we study the travel time estimation for the SP-AS/RS.

After picking products from their storage locations to meet customer demand, transporting rapidly them to customers is also necessary to enhance customer satisfaction in E-Commerce. Therefore, in this thesis, we investigate the multicommodity capacitated network design problem with consolidation constraint (MCNDCC), which originates from Chinese train connection services, and the two-echelon capacitated vehicle routing problem with grouping constraints (2E-CVRPGC), which derives from the freight distribution of many Chinese retailers.


The contributions of this thesis are fourfold. First, we introduce four new optimization problems into the research stream. Second, we formulate analytical and mathematical models for these four problems. Third, we validate the proposed travel time models for the SP-AS/RS and propose effective exact and heuristic algorithms to solve the transportation problems. Finally, we obtain several significant results for the SP-AS/RS, which can provide an academic foundation for future related research and a practical guidance for warehouse managers, and present a set of benchmark instances and experiment results, which facilitate the future researchers to study related problems.

The first problem is the travel time analysis of the DC in the SP-AS/RS with the I/O dwell point policy. In the conventional AS/RS, S/R machines travel simultaneously in the horizontal and vertical directions. However, S/R machines cannot support overly heavy loads, such as sea containers. Therefore, a new AS/RS, called split-platform AS/RS (SP-AS/RS), was introduced and studied in recent years. The SP-AS/RS employs vertical and horizontal platforms, which move independently and are capable of handling heavy loads. The vertical platform, which represents an elevator (or lift) with the elevator's lifting table carries the load up and down among different tiers and the horizontal platform, which represents the shuttle carrier or the shuttle vehicle can access all cells of the tier to which it belongs. The single command cycle (SC) and the dual command cycle (DC) are two main operating modes in AS/RSs. However, the travel time models in all previous articles related to the SP-AS/RS are only for the SC. To address this problem, this thesis first presents a continuous travel time model for the DC in the SP-AS/RS under the input and output (I/O) dwell point policy and validates its accuracy by computer simulations. After comparing it with the existing model for the SC, the DC is found to be better than the SC in terms of the expected travel time.

The second problem is the optimal travel time analysis of the DC in the SP-AS/RS considering two racks with the I/O dwell point policy. This problem is an extension of the first problem. To address the first problem, this thesis proposes a travel time model and finds an upper bound of travel time of the DC in the SP-AS/RS with the I/O dwell point policy. In the second problem, the first step is thus to build a continuous optimal travel time model of the DC in the SP-AS/RS with the I/O dwell point policy. In the above two models, the storage and retrieval operations are in the same rack, so another DC travel time model considering the situation is proposed, where the storage and retrieval operations are located in two adjacent racks. Then, we use convex optimization to analyze the performance of these two proposed models in this problem. Third, we validate these two models by computer simulations and compare the new travel time model for the SP-AS/RS considering one rack with two existing models. Finally, we compare the analytical results of these two proposed models.

The third problem is the multicommodity capacitated network design problem with consolidation constraint (MCNDCC), which originates from Chinese train connection services and has a wide range of applications in other situations. We formulate this problem into an arc-flow model and propose a local branching scheme and a variable neighborhood search (VNS) heuristic to solve it. Both the local branching and the VNS heuristic employ a general mixed integer programming (MIP) solver as a black box to explore neighborhoods defined by the local branching constraints. To evaluate the model and algorithms, we generate a set of railway instances based on the Chinese railway network, and adopt a set of classic benchmark instances originally designed for the multicommodity capacitated network design problem. The computational results show that the general MIP solver ILOG CPLEX can optimally solve the instances of practical size based on the arc-flow model, and both the local branching and the VNS heuristic are able to produce high quality solutions rapidly.

The fourth problem addressed in this thesis is the two-echelon capacitated vehicle routing problem with grouping constraints (2E-CVRPGC), which is a new problem deriving from the classical 2E-CVRP by considering the grouping constraints in the second echelon. Customers in the 2E-CVRPGC are divided into several disjoint groups, and the grouping constraints ensure that customers from the same group are served by vehicles from the same satellite. We propose a mathematical model to formulate the problem and six families of valid inequalities to strengthen the model. Based on the model and valid inequalities, we implement a branch-and-cut algorithm to solve the problem. The proposed branch-and-cut algorithm was tested on two classes of instances generated randomly. Computational results show that the six families of valid inequalities can substantially improve the lower bounds yielded by the LP relaxation of the model, and the branch-and-cut algorithm can solve more instances to optimality than CPLEX. We also conduct additional experiments to analyze the impacts of the grouping constraints on the problem, and illustrate the differences between the 2E-CVRPGC and the 2E-CVRP.

Date of Award	31 Aug 2017
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Leong Chye Andrew LIM (Supervisor) & Xianhao Xu (External Supervisor)