• Regression and classification models quantify and predict route deviations. • Route deviation metrics to measure the similarity of routes. • Models use sequential route structure, route attributes, and driver information. • Exploring tacit driver knowledge for efficient route planning. • Publicly available dataset supports further research. Route planning in last-mile delivery is a complex task with many challenges, directly impacting delivery efficiency and costs. Drivers often deviate from optimized planned routes based on their knowledge. Using the properties of machine learning, this study aims to determine whether machine learning techniques can effectively predict deviations by drivers from planned routes and quantify the extent of such deviations. We propose to predict route deviations by analyzing a logistics company’s historical data of planned and actual routes using deep neural networks, with the dataset made publicly available. Our methodology incorporates both regression and classification models. The regression model estimates the degree of deviation, while the classification model aims to predict whether the deviation from a planned route will exceed a given threshold, based on different deviation metrics. As the input, we leverage the sequential structure of the route with route properties and drivers information. The computational experiments explore extending the given input to the models and testing various state-of-art neural network architectures. Our results demonstrate strong performance on both tasks, with our models achieving 9 − 19 % improvements in regression metrics and 3 − 15 % improvements in classification metrics compared to specified benchmarks, with statistical tests confirming the significance of these improvements.

ABSTRACT Effective planning of human resources is critical in designing an efficient home healthcare system. In this study, we present a novel home healthcare staffing, routing, and scheduling problem inspired by a real‐world application. The proposed problem addresses a set of patients, with varying daily visit requirements, being served by a set of caregivers with different qualification levels over a multi‐day multi‐shift planning horizon. The problem aims to minimize the number of extra shifts for caregivers, maximize the allocation of caregivers to emergencies, and minimize the sum of route durations over the planning horizon. These objectives are optimized hierarchically while considering a set of restrictions, including time windows, skill matching, synchronization, care continuity, and labor regulations. To tackle the problem, we introduce a mixed‐integer linear programming model. The model is then extended and two sets of valid inequalities are incorporated to enhance its tightness. Computational experiments are conducted on a set of 20 instances. The results highlight the efficiency of the proposed extension in increasing both the number of instances that can be solved to optimality and the number of instances for which a feasible solution is found.

Given a directed acyclic graph G=(V,A) and two vertices u,v∈V, the reachability problem is to answer if there is a path from u to v in the graph. In the context of very large graphs, with millions of vertices and a series of queries to be answered, it is not practical to search the graph for each query. On the other hand, the storage of the full transitive closure of the graph is also impractical due to its O(|V|2) size. Scalable approaches aim to create indices used to prune the search during its execution. Negative indices may be able to determine (in constant time) that a query has a negative answer while positive indices may determine (again in constant time) that a query has a positive answer. In this paper we propose a novel scalable approach called LYNX that uses a large number of topological sorts of G as a negative cut index without degrading the query time. A similar strategy is applied regarding a positive cut index. In addition, LYNX proposes a user-defined index size that enables the user to control the ratio between negative and positive cuts depending on the expected query pattern. We show by computational experiments that LYNX consistently outperforms the state-of-the-art approach in terms of query-time using the same index-size for graphs with high reachability ratio. In intelligent computer systems that rely on frequent tests of connectivity in graphs, LYNX can reduce the time delay experience by end users through a reduced query time. This comes at the expense of an increased setup time whenever the underlying graph is updated.

Abstract Increased fuel costs together with environmental concerns have led shipping companies to consider the optimization of vessel speeds. Given a fixed sequence of port calls, each with a time window, and fuel cost as a convex function of vessel speed, we show that optimal speeds can be found in quadratic time. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

In vendor-managed inventory replenishment, the vendor decides when to make deliveries to customers, how much to deliver, and how to combine shipments using the available vehicles. This gives rise to the inventory-routing problem in which the goal is to coordinate inventory replenishment and transportation to minimize costs. The problem tackled in this paper is the stochastic inventory-routing problem, where stochastic demands are specified through general discrete distributions. The problem is formulated as a discounted infinite-horizon Markov decision problem. Heuristics based on finite scenario trees are developed. Computational results confirm the efficiency of these heuristics.

Abstract This paper describes a new Branch‐and‐Regret Heuristic for a class of dynamic and stochastic vehicle routing problems. This work is motivated by a real‐life problem faced by a major transporter in Norway. The heuristic uses stochastic information during the solution process. The new method is shown to be superior to previous heuristics that are uniquely based on a pure dynamic approach. The proposed heuristic is well suited to problems containing stochastic customers, stochastic demands, or both. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 330–340 2007