1,720,968 research outputs found
Real-time schedule adjustments for conflict-free vehicle routing
Full text linkConflict-Free Vehicle Routing Problems (CFVRPs) arise in manufacturing, transportation and logistics applications where Automated Guided Vehicles (AGVs) are utilized to move pallets and containers. A peculiar feature of these problems is that collision avoidance among vehicles must be considered explicitly. To make things more complex, the uncertainty affecting both travel times and machine ready times often results in vehicle delays or anticipations that require real-time modifications to the fleet nominal plan. In this paper, the determination of such modifications (schedule adjustment problem in CFVRPs) is modeled as a sequential decision problem for which we develop a tailored fast exact algorithm suitable for any objective function that is non-decreasing in the arrival times. Computational results show that optimal solutions can be found within at most 3.3 milliseconds for instances with up to 300 vehicles with improvements of various performance measures up to 74% compared to state-of-the-art solution algorithms
An enhanced lower bound for the Time-Dependent Travelling Salesman Problem
No full textGiven a graph whose arc traversal times vary over time, the Time-Dependent Travelling Salesman Problem amounts to find a Hamiltonian tour of least total duration. In this paper we exploit a new degree of freedom in the Cordeau et al. (2014) speed decomposition. This approach results in a parameterized family of lower bounds. The parameters are chosen by fitting the traffic data. The first model is nonlinear and difficult to solve. Hence, we devise a linearization which gives rise to a compact Mixed Integer Linear Programming model. Then, we develop an optimality condition which allows to further reduce the size of the model. Computational results show that, when embedded into a branch-and-bound procedure, this lower bounding mechanism allows to solve to optimality a larger number of instances than state-of-the-art algorithms
A review of recent advances in time-dependent vehicle routing
Full text linkABSTRACT: In late 2015 three of the co-authors of this paper published the first review on time-dependent routing problems. Since then, there have been several important algorithmic developments in the field. These include travel time prediction methods, real-time re-optimization by operating directly on the road graph, efficient exploration of solution neighborhoods, dynamic discretization discovery and Machine Learning-inspired methods. The aim of this survey is to present such research lines, together with indications on their further developments
Crop planting layout optimization in sustainable agriculture: A constraint programming approach
Full text linkIn sustainable agriculture, intercropping systems represent a valuable approach. These systems involve placing
mutually beneficial plant types in close proximity to each other, with the goal of exploiting biodiversity
to reduce pesticide and water usage, as well as improve soil nutrient utilization. Despite its potential, the
optimization of intercropping systems has received limited attention in previous studies. One of the first
steps in the design of an intercropping system is the solution of the crop planting layout problem, which
involves meeting crop demand while maximizing positive interactions between adjacent plants. We perform
a complexity analysis of this problem and solve it through constraint programming, an artificial intelligence
technique, which relies on automated reasoning, constraint propagation and search heuristics. To this aim, we
present two constraint programming models based on integer variables and interval variables, respectively.
Through a computational study on real-life instances, we examine the impact of different modelling approaches
on the difficulty of solving the crop planting layout problem with standard constraint programming solvers.
This research work has also provided the groundwork for a sowing robotic arm (under development), aiming
to automate intercropping systems and assist farm worker
Recovering feasibility in real-time conflict-free vehicle routing
Full text linkConflict-Free Vehicle Routing Problems (CF-VRPs) arise in manufacturing,
transportation and logistics facilities where Automated Guided Vehicles (AGVs)
are utilized to move loads. Unlike \textit{Vehicle Routing Problems} arising in
distribution management, CF-VRPs explicitly consider the limited capacity of
the arcs of the guide path network to avoid collisions among vehicles. AGV
applications have two peculiar features. First, the uncertainty affecting both
travel times and machine ready times may result in vehicle delays or
anticipations with respect to the fleet nominal plan. Second, the relatively
high vehicle speed (in the order of one or two meters per second) requires
vehicle plans to be revised in a very short amount of time (usually few
milliseconds) in order to avoid collisions. In this paper we present fast exact
algorithms to recover plan feasibility in real-time. In particular, we identify
two corrective actions that can be implemented in real-time and formulate the
problem as a linear program with the aim to optimize four common performance
measures (total vehicle delay, total weighted delay, maximum route duration and
total lateness). Moreover, we develop tailored algorithms which, tested on
randomly generated instances of various sizes, prove to be three orders of
magnitude faster than using off-the-shelf solvers
Artificial intelligence and digital reproduction in art
Full text linkIn recent years, AI (artificial intelligence), seen as a set of different technologies
employed in the most diverse fields in emulating human intelligence, undoubtedly represents an extension of human capabilities, but nevertheless cannot substitute it [1]. Its
application can be found not only in the management of civil and social life and economic and political organization [2-3], but also in art and culture [4].
Indeed, as far as AI is concerned, in an area considered unique to human nature,
i.e. creativity, today AI is used in art, a situation which generates both enthusiasm and
perplexity. It is now seen as stimulating creativity, after being considered as having no
value in evaluating that faculty of which human beings are so proud, namely creativity,
in particular, artistic creativity
A Surprisal-Based Greedy Heuristic for the Set Covering Problem
Full text linkIn this paper we exploit concepts from Information Theory to improve the classical Chvatal greedy algorithm for the set covering problem. In particular, we develop a new greedy procedure, called Surprisal-Based Greedy Heuristic (SBH), incorporating the computation of a "surprisal" measure when selecting the solution columns. Computational experiments, performed on instances from the OR-Library, showed that SBH yields a 2.5% improvement in terms of the objective function value over the Chvatal's algorithm while retaining similar execution times, making it suitable for real-time applications. The new heuristic was also compared with Kordalewski's greedy algorithm, obtaining similar solutions in much shorter times on large instances, and Grossmann and Wool's algorithm for unicost instances, where SBH obtained better solutions
Automatic instantiation of a Variable Neighborhood Descent from a Mixed Integer Programming model
No full textIn this paper we describe the automatic instantiation of a Variable Neighborhood Descent procedure from a Mixed Integer Programming model. We extend a recent approach in which a single neighborhood structure is automatically designed from a Mixed Integer Programming model using a combination of automatic extraction of semantic features and automatic algorithm configuration. Computational results on four well-known combinatorial optimization problems show improvements over both a previous model-derived Variable Neighborhood Descent procedure and the approach with a single automatically-designed neighborhood structure. Keywords: Mixed Integer Programming, Variable Neighborhood Descent, Semantic feature
Path and speed optimization for conflict-free pickup and delivery under time windows
No full textThis article introduces a variant of the conflict-free pickup and delivery problem with time windows in which speeds can be regulated. The problem arises in several areas of transportation and logistics including routing and scheduling of automated guided vehicles in port terminals and coordination of unmanned aerial vehicles in controlled airspace. A particular aspect of this problem is that at most one vehicle can traverse an arc of the transportation network at any time. The problem studied in this paper is to determine the vehicle paths and speeds on each arc of the path in such a way that no conflicts arise, the time windows are met, and the total energy consumption is minimized. A branch-and-bound algorithm is described in which a lower bound is obtained by solving a separable nonlinear problem in quadratic time. If the solution of the relaxation is not conflict free, a set of space-based and time-based branching constraints are generated to resolve the detected conflicts. Computational experiments show that, when compared with a state-of-the-art approach, the proposed method is able to generate a larger number of feasible solutions (42% on average) and reduce the computation time by an order of magnitude. Moreover, the approach results in an average energy savings of around 70%
A multi-modal tourist trip planner integrating road and pedestrian networks
Full text linkThe Tourist Trip Design Problem aims to prescribe a sightseeing plan that maximizes tourist satisfaction while taking into account a multitude of parameters and constraints, such as the distances among points of interest, the expected duration of each visit, the opening hours of each attraction, the time available daily. In this article we deal with a variant of the problem in which the mobility environment consists of a pedestrian network and a road network. Hence, a plan includes a car tour with a number of stops from which pedestrian subtours to attractions (each with its own time windows) depart. We study the problem and develop a method to evaluate the feasibility of solutions in constant time, to speed up the search. The proposed method is embedded into an ad-hoc iterated local search. Experimental results show that our approach can handle realistic instances with up to 3643 points of interest (over a seven day planning horizon) in few seconds
- …
