Advances in information technology and telecommunications, together with ever growing amounts of data, offer opportunities for transportation companies to improve the quality of the service that they provide to their customers. This paper compares two methods motivated by the opportunity that the availability of data and technology gives to improve on current practice. In particular, the two solution approaches are explored in the context of a dynamic and stochastic routing problem in which a single, uncapacitated vehicle serves a set of known customers locations. One approach, sample-scenario planning, offers the potential for higher quality solutions, but at the expensive of greater computational effort. On the other hand, anticipatory insertion offers reduced computation and increased managerial ease, but with the potential for reduced solution quality due to restrictions on solution structure. Our results show that anticipatory insertion can often match the quality of sample-scenario planning, particularly when the degree of dynamism is low.

The point-to-point quickest path problem is a classical network optimization problem with numerous applications, including that of computing driving directions. In this paper, we define a lower bound on the time-to-target which is both accurate and fast to compute. We show the potential of this bound by embedding it into an A⁎ algorithm. Computational results on three large European metropolitan road networks, taken from the OpenStreetMap database, show that the new lower bound allows us to achieve an average reduction of 14.36%. This speed-up is valuable for a typical web application setting, where a server needs to answer a multitude of quickest path queries at the same time. Even greater computing time reductions (up to 28.06%) are obtained when computing paths in areas with moderate speeds, e.g. historical city centers.

In this paper we exploit some properties of the travel time model proposed by Ichoua et al (2003), on which most of the current time-dependent vehicle routing literature relies. Firstly, we prove that any continuous piecewise lin- ear travel time model can be generated by an appropriate Ichoua et al (2003) model. We also show that the model parameters can be obtained by solving a system of linear equations for each arc. Then such parameters are proved to be nonnegative if the continuous piecewise linear travel time model satis- es the FIFO property, which allows to interpret them as (dummy) speeds. Finally, we illustrate the procedure through a numerical example. As a by- product, we are able to link the travel time models of a road graph and the associated complete graph over which vehicle routing problems are usually formulated.

This paper deals with Level of Repair Analysis (LORA), which aims at determining appropriated repair policies together with the optimal location of facilities and equipments for the maintenance of complex engineering systems. The aim is to model and solve a single echelon and multi indenture LORA variant, which is more general and realistic than other problems addressed previously. The solution of this problem is faced through the use of an optimization via simulation approach. In particular, we propose a heuristic procedure to explore the search space efficiently through an Approximated Neighbourhood Evaluation (ANE) model, relying on the estimation (via simulation) of a reduced number of parameters.

Given a graph whose arc traversal times vary over time, the Time-Dependent Travelling Salesman Problem (TDTSP) consists in finding a Hamiltonian tour of least total duration covering the vertices of the graph. The contribution of this paper is twofold. First, we describe a lower and upper bounding procedure that requires the solution of a simpler (yet NP-hard) Asymmetric Travelling Salesman Problem (ATSP). In addition, we prove that this ATSP solution is optimal for the TDTSP if all the arcs share a common congestion pattern. Second, we formulate the TDTSP as an integer linear programming model for which valid inequalities are devised. These inequalities are then embedded into a branch-and-cut algorithm that is able to solve instances with up to 40 vertices.

Urban waste management is becoming an increasingly complex task, absorbing a huge amount of resources, and having a major environmental impact. The design of a waste management system consists in various activities, and one of these is related to the location of waste collection sites. In this paper, we propose an integer programming model that helps decision makers in choosing the sites where to locate the unsorted waste collection bins in a residential town, as well as the capacities of the bins to be located at each collection site. This model helps in assessing tactical decisions through constraints that force each collection area to be capacitated enough to fit the expected waste to be directed to that area, while taking into account Quality of Service constraints from the citizens’ point of view. Moreover, we propose an effective constructive heuristic approach whose aim is to provide a good solution quality in an extremely reduced computational time. Computational results on data related to the city of Nardò, in the south of Italy, show that both exact and heuristic approaches provide consistently better solutions than that currently implemented, resulting in a lower number of activated collection sites, and a lower number of bins to be used.

Nowadays, route planning algorithms are commonly used to generate detailed work schedules for solid waste collection vehicles. However, the reliability of such schedules relies heavily on the accuracy of a number of parameters, such as the actual service time at each collection location and the traversal times of the streets (which depend on the specific day of the week and the time of day). In this paper, we propose an automated classification and estimation algorithm that, based on Global Positioning System data collected by the fleet, estimates such parameters in a timely and accurate fashion. In particular, our approach is able to classify automatically events like stops due to traffic jams, stops at traffic lights and stops at collection sites. The system can also be used for automated fleet supervision and in order to notify on a web site whether certain services have been actually provided on a certain day, thus making waste management more accountable to citizens. An experimentation carried out in an Italian municipality shows the advantages of our approach.

In this paper, we study an assembly job shop scheduling problem with tree-structured precedence constraints and jobs characterized by specific bills of materials. We propose a mathematical model to deal with a simplified version of the problem, as well as a fast and efficient constructive heuristic that is able to easily face real-world-sized instances. The production schedule takes into account the actual availability of materials in stock as well as the supply times and the capacity constraints, with the goal to minimize the average delay with respect to the due dates associated to the customers' orders. Computational results on data related to real-life instances show that the mathematical model is able to solve (not always to optimality) small-sized instances only. On the other hand, our heuristic approach is able to solve efficiently very large problems. Moreover, the proposed heuristic turns out to be scalable as the instance size grows.

The definition of a suitable neighborhood structure on the solution space is a key step when designing a heuristic for Mixed Integer Programming (MIP). In this paper, we move on from a MIP compact formulation and show how to take advantage of its features to automatically design efficient neighborhoods, without any human analysis. In particular, we use unsupervised learning to automatically identify "good" regions of the search space "around" a given feasible solution. Computational results on compact formulations of three well-known combinatorial optimization problems show that, on large instances, the neighborhoods constructed by our procedure outperform state-of-the-art domain-independent neighborhoods.

Solid waste management (SWM) is an increasingly complex task, absorbing a huge amount of resources and having a major environmental impact. Computerized systems based on operations research techniques can help decision makers to achieve remarkable cost savings as well as to improve waste recovery. Nevertheless, the literature is quite scattered and disorganized. The objective of this paper is to present an updated survey of the most relevant operations research literature on SWM, mainly focusing on strategic and tactical issues. In addition to providing an extensive bibliographic coverage, we describe the relationships between the various problems, and outline future research.

The scope of this paper is to optimize the performance of a multi-indenture maintenance engineering systems. We focus here on modelling and solving a Level of Repair Analysis (LORA) problem variant with simultaneous determination of resources capacity and spare parts. A solution approach based on optimization via simulation is developed. The simulation phase determines the performance of the whole system taking into account the dynamics of the maintenance processes. The optimization phase explores the search space efficiently through a local search method in order to define a new solution with better performance. Computational results collected while solving an illustrative test problem are reported and discussed.

The paper considers the problem of maximizing the profits of a retailer operating in the Italian electricity market. The problem consists in selecting the contracts portfolio and in defining the bidding strategy in the wholesales market while respecting the technical and regulatory constraints. A novel solution method based on a enhanced discovery of the search domain in the simulated annealing technique has been developed for its solution and a set of realistic test problems have been generated for its validation. The experimental results show that our method outperforms the standard simulated annealing by an improvement gap of 20,48% in average.

This paper deals with the problem of minimizing the sta±ng cost of a same-day courier company subject to service-level requirements. The problem has been modeled as an integer program with non linear probabilistic constraints. We have devised a heuristic procedure able to explore the search space e±ciently through an approximated neighborhood evaluation (ANE) model, relying on the estimation (via simulation) of a reduced number of parameters. Computational results show that, compared to traditional neighborhood search procedures, the ANE approach provides signi¯cant cost reductions in a typical same-day courier setting.

Urban waste management is becoming an increasingly complex task, absorbing a huge amount of resources, and having a major environmental impact. The design of a waste management system consists in various activities, and one of these is related to the definition of shift schedules for both personnel and vehicles. This activity has a great incidence on the tactical and operational cost for companies. In this paper, we propose an integer programming model to find an optimal solution to the integrated problem. The aim is to determine optimal schedules at minimum cost. Moreover, we design a fast and effective heuristic to face large-size problems. Both approaches are tested on data from a real-world case in Southern Italy and compared to the current practice utilized by the company managing the service, showing that simultaneously solving these problems can lead to significant monetary savings.

In this paper, we deal with single machine scheduling problems subject to time dependent effects. The main point in our models is that we do not assume a constant processing rate during job processing time. Rather, processing rate changes according to a fixed schedule of activities, such as replacing a human operator by a less skilled operator. The contribution of this paper is threefold. First, we devise a time-dependent piecewise constant processing rate model and show how to compute processing time for a resumable job. Second, we prove that any time-dependent continuous piecewise linear processing time model can be generated by the proposed rate model. Finally, we propose polynomial-time algorithms for some single machine problems with job independent rate function. In these procedures the job-independent rate effect does not imply any restriction on the number of breakpoints for the corresponding continuous piecewise linear processing time model. This is a clear element of novelty with respect to the polynomial-time algorithms proposed in previous contributions for time-dependent scheduling problems.

In the Job Sequencing and Tool Switching Problem (SSP) a number of part types, each requiring a set of tools, are to be manufactured on a single flexible machine with a capacitated tool magazine. The SSP aims at determining the processing sequence as well as the tools present in the magazine for each part, in order to minimize the total number of tools switches. In this paper, we cast the SSP as a nonlinear least cost Hamiltonian cycle problem. A branch-and-cut algorithm is proposed and compared to previous exact procedures. Computational results indicate that the algorithm is able to solve much larger instances than those reported in the literature.

In this paper, we study two decisional problems arising when planning the collection of solid waste, namely the location of collection sites (together with bin allocation) and the zoning of the service territory, and we assess the potential impact that an efficient location has on the subsequent zoning phase. We first propose both an exact and a heuristic approach to locate the unsorted waste collection bins in a residential town, and to decide the capacities and characteristics of the bins to be located at each collection site. A peculiar aspect we consider is that of taking into account the compatibility between the different types of bins when allocating them to collection areas. Moreover, we propose a fast and effective heuristic approach to identify homogeneous zones that can be served by a single collection vehicle. Computational results on data related to a real-life instance show that an efficient location is fundamental in achieving consistent monetary savings, as well as a reduced environmental impact. These reductions are the result of one vehicle less needed to perform the waste collection operations, and an overall traveled distance reduced by about 25% on the average.

This paper deals with an exact algorithm for the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW) with continuous piecewise linear cost functions. There are two main research streams that can benefit from efficient exact algorithms for TDTSPTW. The first concerns determining optimal vehicle route planning taking traffic congestion into account explicitly. The latter deals with sequence dependent set-up single machine scheduling problems minimizing total completion times or total tardiness. The contribution of this paper is twofold. First, it is proved that the Asymmetric Traveling Salesman Problem with Time Windows is optimal for the TDTSPTW, if all the arcs share a common congestion pattern. Second, an integer linear programming model is formulated for TDTSPTW, and valid inequalities are then embedded into a branch-and-cut algorithm. Preliminary results show that the proposed algorithm is able to solve instances with up to 67 vertices.

The fast computation of point-to-point quickest paths on very large time-dependent road networks will allow next-generation web-based travel information services to take into account both congestion patterns and real-time traffic informations. The contribution of this article is threefold. First, we prove that, under special conditions, the Time-Dependent-Quickest Path Problem (QPP) can be solved as a static QPP with suitable-defined (constant) travel times. Second, we show that, if these special conditions do not hold, the static quickest path provides a heuristic solution for the original time-dependent problem with a worst-case guarantee. Third, we develop a time-dependent lower bound on the time-to-target which is both accurate and fast to compute. We show the potential of this bound by embedding it into a unidirectional A* algorithm which is tested on large metropolitan graphs. Computational results show that the new lower bound allows to reduce the computing time by 27% on average.

Time-dependent routing amounts to design “best” routes in a graph in which arc traversal times may vary over the planning horizon. In the last decade, a number of technological advances have stimulated an increased interest in this field. We survey the research in the area and present a comprehensive review of travel time modelling, applications and solution methods. In particular, we make a first classification in point-to-point and multiple-point problems. A second major classification is then performed with respect to the quality and evolution of information. Other criteria included: (i) node, arc or general routing; (ii) the possibility to choose the vehicle speed.

La società ha per obiettivo primario la valorizzazione dei risultati della ricerca svolta all'interno dell'Università attraverso lo sviluppo di nuovi prodotti e servizi nel campo della formazione e della ricerca socio economica, della finanza, dell'ingegneria gestionale, del project design e del project management, ed in particolare quella sviluppata presso l'Università del Salento nel campo della: governance territoriale, cooperazione e valutazione delle politiche; analisi statistico socio-economiche e di mercato; business engineering; project design e management; formazione