Traditional car sharing services have been based on the two‐way scheme, where the user picks up and returns the vehicle at the same parking station. Some innovative services permit also one‐way trips, that is, the user is allowed to return the vehicle in another station. The one‐way scheme is more attractive for the users, but may lead to an unbalance between the user demand, and the availability of vehicles or free lots at the stations. In such cases, the service provider could reallocate the fleet and restore a better distribution of the vehicles among the stations. In the case of electric car sharing, such a problem is more complex because the travel range depends on the level of the battery charge. This article presents a new approach for the relocation of electric vehicles (EVs), carried out by the staff of the service provider to keep the system balanced. Such an approach generates a challenging Paired Pickup and Delivery Problem with Time Windows with new features that to the best of our knowledge have never been considered in the literature. We call such a problem the EV relocation problem (EVRP). We yield a mixed integer linear programming (MILP) formulation of the EVRP and some techniques to speedup its solution through a state‐of‐the‐art solver (CPLEX). Moreover, we develop a simple but effective heuristic based on such a formulation and four upper bound generation methods. We test the performances of both the MILP formulation and the heuristic on instances built on the Milan road network. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 292–305 2014

In recent years, there has been growing interest in algorithms inspired by the observation of natural phenomena to define computational procedures that can solve complex problems. We describe a distributed heuristic algorithm that was inspired by the observation of the behavior of ant colonies, and we propose its use for the quadratic assignment problem. The results obtained in solving several classical instances of the problem are compared with those obtained from other evolutionary heuristics to evaluate the quality of the proposed system.

An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic helps find acceptable solutions in the early stages of the search process. We apply the proposed methodology to the classical traveling salesman problem (TSP), and report simulation results. We also discuss parameter selection and the early setups of the model, and compare it with tabu search and simulated annealing using TSP. To demonstrate the robustness of the approach, we show how the ant system (AS) can be applied to other optimization problems like the asymmetric traveling salesman, the quadratic assignment and the job-shop scheduling. Finally we discuss the salient characteristics-global data structure revision, distributed communication and probabilistic transitions of the AS.