Formulating and solving integrated order batching and routing in multi-depot AGV-assisted mixed-shelves warehouses

• URL: http://arxiv.org/abs/2101.11473v1
• Date: Wed, 27 Jan 2021 15:04:05 GMT
• Title: Formulating and solving integrated order batching and routing in multi-depot AGV-assisted mixed-shelves warehouses
• Authors: Lin Xie, Hanyi Li and Laurin Luttmann
• Abstract summary: This paper proposes a mixed-shelves storage policy and AGV-assisted mixed-shelves picking systems. We develop a variable neighborhood search algorithm to solve the integrated problem more efficiently. We conclude that the mixed-shelves storage policy is more suitable than the usual storage policy in AGV-assisted mixed-shelves systems for both single-line and multiline orders.
• Score: 1.2117737635879038
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Different retail and e-commerce companies are facing the challenge of assembling large numbers of time-critical picking orders that include both single-line and multi-line orders. To reduce unproductive picker working time as in traditional picker-to-parts warehousing systems, different solutions are proposed in the literature and in practice. For example, in a mixed-shelves storage policy, items of the same stock keeping unit are spread over several shelves in a warehouse; or automated guided vehicles (AGVs) are used to transport the picked items from the storage area to packing stations instead of human pickers. This is the first paper to combine both solutions, creating what we call AGV-assisted mixed-shelves picking systems. We model the new integrated order batching and routing problem in such systems as an extended multi-depot vehicle routing problem with both three-index and two-commodity network flow formulations. Due to the complexity of the integrated problem, we develop a novel variable neighborhood search algorithm to solve the integrated problem more efficiently. We test our methods with different sizes of instances, and conclude that the mixed-shelves storage policy is more suitable than the usual storage policy in AGV-assisted mixed-shelves systems for both single-line and multi-line orders (saving up to 67% on driving distances for AGVs). Our variable neighborhood search algorithm provides close-to-optimal solutions within an acceptable computational time.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Solving Complex Multi-UAV Mission Planning Problems using Multi-objective Genetic Algorithms [4.198865250277024]
  This paper presents a new Multi-Objective Genetic Algorithm for solving complex Mission Planning Problems (MPP) A hybrid fitness function has been designed using a Constraint Satisfaction Problem (CSP) to check if solutions are valid. Experimental results show that the new algorithm is able to obtain good solutions, however as the problem becomes more complex, the optimal solutions also become harder to find.
  arXiv  Detail & Related papers  (2024-02-09T16:13:21Z)
• Multi-Agent Learning of Efficient Fulfilment and Routing Strategies in E-Commerce [11.421159751635667]
  paper presents an integrated algorithmic framework for minimising product delivery costs in e-commerce. One of the major challenges in e-commerce is the large volume of-temporally diverse orders from multiple customers. We propose an approach that combines graph neural networks and reinforcement learning to train the node selection and vehicle agents.
  arXiv  Detail & Related papers  (2023-11-20T10:32:28Z)
• DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments [55.204450019073036]
  We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
  arXiv  Detail & Related papers  (2022-09-07T00:35:27Z)
• Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF) We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.
  arXiv  Detail & Related papers  (2022-02-08T07:26:45Z)
• Reinforcement learning for multi-item retrieval in the puzzle-based storage system [0.694936386455667]
  This work develops a deep reinforcement learning algorithm to solve the multi-item retrieval problem in the puzzle-based storage system. Extensive numerical experiments demonstrate that the reinforcement learning approach can yield high-quality solutions. A conversion algorithm and a decomposition framework are proposed to handle simultaneous movement and large-scale instances.
  arXiv  Detail & Related papers  (2022-02-05T12:39:21Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)
• Exploration in two-stage recommender systems [79.50534282841618]
  Two-stage recommender systems are widely adopted in industry due to their scalability and maintainability. A key challenge of this setup is that optimal performance of each stage in isolation does not imply optimal global performance. We propose a method of synchronising the exploration strategies between the ranker and the nominators.
  arXiv  Detail & Related papers  (2020-09-01T16:52:51Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Solving Area Coverage Problem with UAVs: A Vehicle Routing with Time Windows Variation [0.0]
  In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. We address this by considering a Vehicle Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs.
  arXiv  Detail & Related papers  (2020-03-16T11:27:21Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.