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.

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.

Over the last decades, the production of “sustainable energy” has provided a very fertile research field, involving aspects that are traditionally considered in an independent manner, namely renewable energy production, energy storage and efficient usage of available energy. A combined analysis of these three aspects within an industrial context is the main focus of this work. We provide an insight on the problems that a small or medium manufacturing firm can expect to address when it decides to move from traditional energy suppliers to an as much as possible autonomous energy production. In particular, we consider the contribution that ICT can offer in order to allow the firm to decide the best size and composition of its own “energy production plant”, based on data regarding its production needs and weather-related data. We propose an open source framework aimed at making it possible to model various systems including both energy production, storage and consumption elements. The framework also allows the use of different approaches to optimize and fine tune the system in terms of both design and usage costs. We show how the framework can be specialized in order to be used for a typical industrial test case representing a small medium manufacturing firm that decides to change its position from a pure energy consumer to an energy combined producer, storer and user.

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.

From the early 1990s, the introduction of high-throughput clinical analyzers has significantly changed the workflow of In-Vitro-Diagnostics (IVD) tests. These high-tech instruments have helped and keep helping clinical laboratories both to increase quality diagnostic responses and to get more for every dollar they spend. Nevertheless, IVD industrial research has been up to now largely hardware-driven with the introduction in the market of many sophisticated technologies. The software component, models and decision support systems in particular, has lagged behind. To reach the full potential of diagnostic automation, it must be addressed the challenge of making the most intelligent use of the hardware that is deployed. Focusing on time efficiency, the authors have devised an operations research-based method for a class of high-throughput clinical analyzers. To demonstrate the validity of the research, the proposed method has been coded and integrated into the Laboratory Information System of the Laboratorio di Analisi Cliniche Dr. P. Pignatelli, one of the most important clinical laboratories in Southern Italy. Siemens Immulite ®; 2000 has been the reference case. The enhanced operating planning procedure provides a monetary benefit of 52,000 USD/year per instruments and a trade-off between clinical benefits and operating costs equivalent to the one provided by the current hardware-driven research at Siemens. Despite the proposed approach has the potential to determine guidelines for enhancing a wide range of current high-throughput clinical analyzers, we have to register a failure in trying to convince technology providers to invest in embedding such new models in their hardware. Some possible causes for such failure are highlighted, trying to find possible improvements for future developments.

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.