1,721,088 research outputs found
Emerging optimization problems for distribution in same-day delivery
No full textSame-day delivery (SDD) has become a new standard to satisfy the "instant gratification" of online customers. Despite existing powerful technologies deployed in last-mile delivery, SDD services face new decision-making challenges on the tradeoff between delivery costs and time. In addition, new concerns on environmental issues, customer satisfaction, and fairness arise. Researchers have explored various approaches to face these challenges in SDD, where data uncertainty plays a fundamental role. In this paper, we carefully review the emerging routing problems and solutions proposed in the existing literature for SDD services. We survey papers on how to manage dynamic order arrivals, how to allocate time slots for deliveries, how to select the right delivery options, how to design pickup and delivery routes, and how to partition delivery areas and decide the composition of the fleet. We also propose mathematical formulations for representative problems. Finally, we sketch managerial insights and identify future research directions
Tactical workforce sizing and scheduling decisions for last-mile delivery
No full textWe tackle the problems of workforce sizing and shift scheduling of a logistic operator delivering parcels in the last-mile segment of the supply chain. Our working hypothesis is that the relevant decisions are affected by two main trade-offs: workforce size and shift stability. A large workforce can deal with demand fluctuations but incurs higher fixed costs; by contrast, a small workforce might require excessive outsourcing to third-party logistic providers. Stable shifts, i.e., with predictable start times and lengths, improve worker satisfaction and reduce turnover; at the same time, they might be less able to adapt to an unsteady demand. We test these assumptions through an extensive computational campaign based on a novel mathematical formulation. We find that extreme shift stability is, indeed, unsuitable for last-mile operations. At the same time, introducing a very limited amount of flexibility achieves similar effects as moving to a completely flexible system while ensuring a better work-life balance for the workers. Several recent studies in the social sciences have warned about the consequences of precarious working conditions for couriers and retail workers and have recommended - among other things - stable work schedules. Our work shows that it is possible to offer better working conditions in terms of shift stability without sacrificing the company's bottom line. Thus, companies prioritising profitability (as is often the case) can improve workers' well-being and increase retention with a negligible cost impact
Reinforcement Learning Approaches for the Orienteering Problem with Stochastic and Dynamic Release Dates
No full textIn this paper, we study a sequential decision-making problem faced by e-commerce carriers related to when to send out a vehicle from the central depot to serve customer requests and in which order to provide the service, under the assumption that the time at which parcels arrive at the depot is stochastic and dynamic. The objective is to maximize the expected number of parcels that can be delivered during service hours. We propose two reinforcement learning (RL) approaches for solving this problem. These approaches rely on a look-ahead strategy in which future release dates are sampled in a Monte Carlo fashion, and a batch approach is used to approximate future routes. Both RL approaches are based on value function approximation: One combines it with a consensus function (VFA-CF) and the other one with a two-stage stochastic integer linear programming model (VFA-2S). VFA-CF and VFA-2S do not need extensive training as they are based on very few hyperparameters and make good use of integer linear programming (ILP) and branch-and-cut-based exact methods to improve the quality of decisions. We also establish sufficient conditions for partial characterization of optimal policy and integrate them into VFA-CF/VFA-2S. In an empirical study, we conduct a competitive analysis using upper bounds with perfect information. We also show that VFA-CF and VFA-2S greatly outperform alternative approaches that (1) do not rely on future information (2) are based on point estimation of future information, (3) use heuristics rather than exact methods, or (4) use exact evaluations of future rewards
Matheuristic Algorithms for the Inventory Routing Problem With Unsplit and Split Deliveries
No full textWe introduce new matheuristic algorithms for the Inventory Routing Problem with unsplit and split deliveries for both Order-Up-to Level and Maximum Level replenishment policies. The first matheuristic is based on the Capacitated Concentrator Location problem. The second is a route-based approach using routes found in other schemes as input, including the ones found in the first matheuristic. We carry out extensive experiments on benchmark instances to understand their effectiveness. The results show that they are effective and require a relatively short computational time
A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance
No full textThis paper addresses a variant of the classical Traveling Salesman Problem known as Close-Enough Traveling Salesman Problem. In this problem, there is a set of nodes (customers, targets), each of them associated with a region, denoted as neighborhood, that contains it. The goal is to determine the shortest tour that visits all the nodes, where a node is visited when the tour traverses or reaches the region associated with the node. We propose a genetic algorithm (GA), which uses several strategies to optimize the tour, such as 2opt, second-order cone programming, and a bisection algorithm. The proposed approach is tested on 62 benchmark instances. The results show that GA produces better or similar solutions compared to the ones produced by state-of-the-art algorithms in a reasonable computing time. Besides, GA found 32 new best solutions out of 62 instances. Furthermore, we propose different metrics to classify problem instances with the goal of detecting which problem characteristics have a larger impact on the difficulty of solving the problem. We also revised the already proposed metric, called Overlap Ratio, and correct its calculation done in previous contributions. Finally, we present a case study related to the diagnostic reconnaissance of solar panels. The case study is related to a research project developed at the University of Molise in collaboration with private IT companies. We show that the problem under study is properly modeled as a Close-Enough Traveling Salesman Problem and apply the GA to solve it, focusing on the benefits obtained by applying this solution approach
Recent challenges in Routing and Inventory Routing: E‐commerce and last‐mile delivery
No full textIn the e-commerce era, vendors have to satisfy a large number of on-line orders, mainly from private customers, with low weight and volume, reduced delivery time, and overlap of customers' time windows. Production is made available all day long. New strategies and new technologies are emerging for deliveries. The processing time of the orders is reduced. These new features generate interesting challenges in formulating and solving Routing and Inventory Routing problems. After discussing these features and the corresponding challenges, we recall the relevant literature in Routing and Inventory Routing and provide future research directions, mainly related to routing problems with release dates, routing problems with crowdshipping, and inventory routing problems in the e-commerce era
Integrating public transport in sustainable last-mile delivery: Column generation approaches
No full textNeural combinatorial optimization: A tutorial
No full textRecent advancements in deep reinforcement learning have sparked a growing interest in the application of this approach to solve combinatorial optimization (CO) problems. This paper presents neural combinatorial optimization (NCO) as a framework for constructing functions that work as heuristics for CO problems. Given the rapid expansion of the field and the increasing interest in the topic, this tutorial introduces the main techniques utilized in NCO and explores the current open issues in the field. We define key terms and concepts related to NCO and present the latest developments, using the Knapsack Problem as a running example to complement theoretical explanations. Finally, we analyze prominent works in the field of NCO, with a focus on their application to the Traveling Salesman Problem, which serves as the most extensively studied problem in this domain
A column generation-based matheuristic for an inventory-routing problem with driver-route consistency
No full textThis paper investigates a variant of an inventory-routing problem (IRP) that enforces two conditions on the structure of the solution: time-invariant routes, and a fixed, injective (i.e., one-to-one) assignment of routes to vehicles. The practical benefits of concurrent route invariance and driver assignments are numerous. Fixed routes reduce the solution space of the problem and improve its tractability; they simplify operations; and they increase the viability of newer delivery technologies like drones and autonomous vehicles. Consistency between driver and customer is linked to improved service, driver job satisfaction and delivery efficiency, and is also an important consideration in certain contexts like home healthcare. After formulating the problem a mixed integer-linear program, we recast it as a set partitioning problem whose linear relaxation is solved via column generation. Due to the prohibitively expensive nature of the pricing problem that generates new columns, we present a novel column generation-based heuristic for it that relies on decoupling routing and inventory management decisions. We demonstrate the effectiveness of the proposed method via a numerical study
- …
