Abstract

Projet PRAXITELE; For a large urban area an alternative to public transportation and private cars is considered in the form of a "free" use of electric cars. Such "free" use of electric cars would require periodic redistribution of the cars among different dropoff/pickup stations by a fleet of finite capacity towtrucks stationed at the various depots on the road network. In this study we examine in detail the electric car redistribution problem. The redistribution activity is modelled as that of less than truck load, pickup and delivery with nonsimple paths, allowing for split pickups and deliveries. We propose a Mixed Integer Programming formulation of the problem and we test several solution which include constraint Programming, Lagrangian relaxation methodology applied to the MIP model, and an AI solution approach with a modified A* heuristic. The solution procedures here are designed to solve large practical instances of the car redistribution problem.