Explore the vast range of titles available.

In order to foster electric vehicle (EV) adoption rates, the availability of a pervasive and efficient charging network is a crucial requirement. In this paper, we provide a decision support tool for helping policymakers to locate and size EV charging stations. We consider a multi-year planning horizon, taking into account different charging technologies and different time periods (day and night). Accounting for these features, we propose an optimization model that minimizes total investment costs while ensuring a predetermined adequate level of demand coverage. In particular, the setup of charging stations is optimized every year, allowing for an increase in the number of chargers installed at charging stations set up in previous years. We have developed a tailored heuristic algorithm for the resulting problem. We validated our algorithm using case study instances based on the village of Gardone Val Trompia (Italy), the city of Barcelona (Spain), and the country of Luxembourg. Despite the variability in the sizes of the considered instances, our algorithm consistently provided high-quality results in short computational times, when compared to a commercial MILP solver. Produced solutions achieved optimality gaps within 7.5% in less than 90 s, often achieving computational times of less than 5 s.

A number of decision support tools facilitating the use of Electric Vehicles (EVs) have been recently developed. Due to the EVs’ limited autonomy, routing and path planning are the main challenges treated in such tools. Specifically, determining at which Charging Stations (CSs) to stop, and how much the EV should charge at them is complex. This complexity is further compounded by the fact that charging times depend on the CS technology, the EV characteristics, and follow a nonlinear function. Considering these factors, we propose a path-planning methodology for EVs with user preferences, where charging is performed at public CSs. To achieve this, we introduce the Electric Vehicle Shortest Path Problem with time windows and user preferences (EVSPPWP) and propose an efficient heuristic algorithm for it. Given an origin and a destination, the algorithm prioritizes CSs close to Points of Interest (POIs) that match user inputted preferences, and user-defined time windows are considered for activities such as lunch and spending the night at hotels. The algorithm produces flexible solutions by considering clusters of charging points (CPs) as separate CSs. Furthermore, the algorithm yields resilient paths by ensuring that recommended paths have a minimum number of CSs in their vicinity. The main contributions of our methodology are the following: modeling user-defined time windows, including user-defined weights for different POI categories, creating CSs based on clusters of CPs with sufficient proximity, using resilient paths, and proposing an efficient algorithm for solving the EVSPPWP. To facilitate the use of our methodology, the algorithm was integrated into a web interface. We demonstrate the use of the web interface, giving usage examples and comparing different settings.

Local public transport companies, especially in large cities, are facing every day the problem of managing delays and small disruptions. Disruption management is a well-established practice in airlines and railways. However, in local public transport the approaches to these problems have followed a different path, mainly focusing on holding and short-turning strategies not directly associated with the driver scheduling. In this paper we consider the case of the management of urban surface lines of Azienda Trasporti Milanese (ATM) of Milan. The main issues are the service regularity as a measure of the quality of service, and the minimization of the operational costs due to changes in the planned driver scheduling. We propose a simulation-based optimization system to cope with delays and small disruptions that can be effectively used in a real-time environment and takes into account both vehicle and driver scheduling. The proposed approach is tested on real data to prove its actual applicability.

In this paper, we introduce the Pick and Place Packaging Problem (P4), for optimally scheduling a packaging system with one input conveyor (pick) and one output conveyor (place). We give a formal definition of the underlying dynamic optimization problem. We describe two properties that hold for its solutions and present an efficient row generation approach exploiting these properties. Starting from a basic version of the problem, we introduce two variants where we account for the possibility of holding the grip of items and variable conveyor speed. We extend the proposed exact solution method to these two cases. Then, we present an efficient Iterated Local Search heuristic for the problem and its variants. Numerical results show the effectiveness of our approach.

We address a particular pickup and delivery vehicle routing problem arising in the collection and disposal of bulky recyclable waste. Containers of different types, used to collect different waste materials, once full, must be picked up to be emptied at suitable disposal plants and replaced by empty containers alike. All requests must be served, and routes are subject to a maximum duration constraint. Minimizing the number of vehicles is the main objective, while minimizing the total route duration is a secondary objective. The problem belongs to the class of rollon–rolloff vehicle routing problems (RR-VRPs), though some characteristics of the case study, such as the free circulation of containers and the limited availability of spare containers, allow us to exploit them in the solution approach. We formalize the problem as a special vehicle routing problem on a bipartite graph, we analyze its structure, and we compare it to similar problems emphasizing the impact of limited spare containers. Moreover, we propose a neighborhood-based metaheuristic that alternatively switches from one objective to the other along the search path and periodically destroys and rebuilds parts of the solution. The main algorithm components are experimentally evaluated on real and realistic instances, the largest of which fail to be solved by a mixed-integer linear programming solver. We are increasingly competitive with the solver as the instance size increases, especially regarding fleet size. In addition, the algorithm is applied to the benchmark instances for the RR-VRP.

The planning of metro lines is typically done through a strictly hierarchical approach, which is effective but somewhat inflexible. In this paper, we propose a flexible semiperiodic timetabling strategy using short-turning; thus, allowing trains to turn before reaching the terminal station of a line. Our strategy produces timetables that are periodic with respect to a group of short-turning destinations. This is denoted by the term service pattern. We introduce the service pattern timetabling problem (SPTP). Given a service pattern, the SPTP optimizes the train timetable considering capacity restrictions. The SPTP is modeled as a constraint program. We develop a framework for producing a large set of diverse and high-quality timetables for a metro line. This is achieved by repeatedly solving the SPTP with different patterns. Then we select a restricted list of non-dominated solutions with respect to three objectives: (1) the average passenger waiting time, (2) the maximum load factor achieved by the trains, and (3) the number of transfers induced by short-turning. We evaluate the proposed framework on a number of test instances. Through our computational experiments, we demonstrate the effectiveness of the developed strategy.

This paper surveys recent applications and advances of the Constraint Programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by Constraint Programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using Constraint Programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the Constraint Programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.

Radio planning and coverage optimization are critical issues for service providers and vendors that are deploying third generation mobile networks and need to control coverage as well as the huge costs involved. Due to the peculiarities of the Code Division Multiple Access (CDMA) scheme used in 3G cellular systems like UMTS and CDMA2000, network planning cannot be based only on signal predictions, and the approach relying on classical set covering formulations adopted for second generation systems is not appropriate. In this paper we investigate mathematical programming models for supporting the decisions on where to install new base stations and how to select their configuration (antenna height and tilt, sector orientations, maximum emission power, pilot signal, etc.) so as to find a trade-off between maximizing coverage and minimizing costs. The overall model takes into account signal-quality constraints in both uplink and downlink directions, as well as the power control mechanism and the pilot signal. Since even small and simplified instances of this NP-hard problem are beyond the reach of state-of-the-art techniques for mixed integer programming, we propose a Tabu Search algorithm which provides good solutions within a reasonable computing time. Computational results obtained for realistic instances, generated according to classical propagation models, with different traffic scenarios (voice and data) are reported and discussed.

We present the symmetric traveling salesman problem with generalized latency (TSP-GL) a new problem arising in the planning of the important class of semiflexible transit systems. The TSP-GL can be seen as a very challenging variant of the symmetric traveling salesman problem (S-TSP), where the objective function combines the usual cost of the circuit with a routing component accounting for the passenger travel times. The main contributions of the paper include the formulation of the problems in terms of multicommodity flows, the study of its mathematical properties, and the introduction of a branch-and-cut approach based on Benders reformulation taking advantage of properties that relate the feasible region of the TSP-GL and the S-TSP polyhedron. An extensive computational experimentation compares a number of variants of the proposed algorithm, as well as a commercial solver. These experiments show that the method we propose significantly outperforms a well-known commercial solver and obtains good-quality solutions to realistically sized instances within short computational times.

Demand-Adaptive Systems (DASs) display features of both traditional fixed-line bus services and purely on-demand systems such as dial-a-ride, that is, they offer demand-responsive services within the framework of traditional scheduled bus transportation. A DAS bus line serves a given set of compulsory stops according to a predefined schedule, which specifies the time windows associated with each stop, and thus provides the traditional use of a transit line without reservation. On the other hand, passengers may issue requests for transportation between two optional stops, inducing detours in the vehicle routes. The design of a DAS line is a complex planning process that requires to select the compulsory stops and to determine its master schedule in terms of the time windows associated with the compulsory stops. In this paper, we focus on determining the master schedule for a single DAS line. We propose a mathematical description and a solution method based on probabilistic approximations of several DAS line core characteristics. Results of numerical experiments are also given and analyzed.