There is an increasing interest in sustainability and a growing debate about environmental policy measures aiming at the reduction of green house gas emissions across di erent economic sectors worldwide. The transportation sector is one major greenhouse gas emitter which is heavily regulated to reduce its dependance on oil. These regulations along with the growing customer awareness about global warming has led vehicle manufacturers to seek di erent technologies to improve vehicle e ciencies and reduce the green house gases emissions while at the same time meeting customer's expectation of mobility and exibility. Plug-in hybrid electric vehicles (PHEV) is one major promising solution for a smooth transition from oil dependent transportation sector to a clean electric based sector while not compromising the mobility and exibility of the drivers. In the medium term, plug-in hybrid electric vehicles (PHEV) can lead to signi cant reductions in transportation emissions. These vehicles are equipped with a larger battery than regular hybrid electric vehicles which can be recharged from the grid. For short trips, the PHEV can depend solely on the electric engine while for longer journeys the alternative fuel can assist the electric engine to achieve extended ranges. This is bene cial when the use pattern is mixed such that and short long distances needs to be covered. The plug-in hybrid electric vehicles are well-suited for logistics since they can avoid the possible disruption caused by charge depletion in case of all-electric vehicles with tight time schedules. The use of electricity and fuel gives rise to a new variant of the classical vehicle routing with time windows which we call the plug-in hybrid electric vehicle routing problem with time windows (PHEVRPTW). The objective of the PHEVRPTW is to minimize the routing costs of a eet of PHEVs by minimizing the time they run on gasoline while meeting the demand during the available time windows. As a result, the driver of the PHEV has two decisions to make at each node: (1) recharge the vehicle battery to achieve a longer range using electricity, or (2) continue to the next open time window with the option of using the alternative fuel. In this thesis, we present a mathematical formulation for the plug-in hybrid-electric vehicle routing problem with time windows. We solve this problem using a Lagrangian relaxation and we propose a new tabu search algorithm. We also present the rst results for the full adapted Solomon instances.

Expanderande städer resulterar i ökande behov av godstransporter och för att behålla en fungerande godsdistribution kan åtgärder behöva vidtas. Trafikstockning och försämrad stadsmiljö är negativa effekter som kan förknippas med en dåligt fungerande godsdistribution. Citylogistik handlar om att kontrollera och optimera godstransporter i urbana områden (city) så att negativa effekter minimeras. Olika typer av citylogistiska åtgärder och koncept har identifierats. Till dem hör till exempel samdistribution, reglering av godstransporter och avancerade IT-system. Inom ramen för projektet SAMLIC, som startades i Linköping 2004, genomfördes pilotförsöket PILOT med det övergripande syftet att utvärdera ekonomisk potential med samdistribution i Linköpings city. Under PILOT omsattes ett samdistributionskoncept i praktiken. En databas med information om godsdistributionen under försöket upprättades för senare analys. Syftet med detta examensarbete har varit att formulera matematiska modeller över godsdistributionen i ett medelstort city, som kan ge underlag för utvärdering av citylogistiska koncept och i synnerhet samdistributionskoncept. De matematiska modeller som tagits fram är optimeringsmodeller för ruttplanering och metoder för att lösa optimeringsmodellerna har implementerats. För att utvärdera modellerna och metoderna har en fallstudie av Linköpings city gjorts, med datamaterial från PILOT. Modellerna ger möjlighet till effektiva analyser och jämförelser av citylogistiska koncept. Fallstudien visar dessutom att optimering av godsdistributionen i city innebär god förbättringspotential vilket ger ytterligare motiv till att använda modeller som verktyg. / Urbanization and city expansion result in an increasing need of transportation of goods, and in order to maintain efficiency, measures are needed. The aim of city logistics is to minimize negative impacts associated with city center goods distribution, such as traffic congestion and negative impacts on the living environment. Several city logistic measures have previously been suggested, such as freight consolidation, governance and advanced IT systems. Within the SAMLIC project started in 2004, a demonstration project known as PILOT was carried out in central Linköping, wherein the concept of freight consolidation was applied in reality. The objective was to evaluate the economic potential of freight consolidation. The aim of this thesis was to formulate mathematical models of the distribution of goods in a medium sized Swedish city. The models are to be used in the evaluation of city logistic measures, focusing on freight consolidation. The distribution problem is modelled as a vehicle routing problem, and methods for solving the resulting optimization problems have been implemented. Using data from PILOT, the models have been applied on Linköping with the purpose of evaluating the methods, as well as investigating the potential of using models for planning the distribution of goods. Conclusions involve that analyses of, and comparisons between, city lo-gistic measures can be efficiently made using mathematical models. The case study also indicates that goods distribution can be improved through the use of optimization methods, which further motivates mathematical modelling.

This dissertation focuses on improvements in vehicle routing that can be gained by allowing multiple vehicles to service a common load. We explore how costs can be reduced through the elimination of the constraint that a load must be serviced by only one vehicle. Specifically, we look at the problem of routing vehicles to service loads that have distinct origins and destinations, with no constraint on the amount of a load that a vehicle may service. We call this the Pickup and Delivery Problem with Split Loads (PDPSL). We model this problem as a dynamic program and introduce structural results that can help practitioners implement the use of split loads, including the definition of an upper bound on the benefit of split loads. This bound indicates that the routing cost can be reduced by at most one half when split loads are allowed. Furthermore, the most benefit occurs when load sizes are just above one half of vehicle capacity. We develop a heuristic for the solution of large scale problems, and apply this heuristic to randomly generated data sets. Various load sizes are tested, with the experimental results supporting the finding that most benefit with split loads occurs for load sizes just above one half vehicle capacity. Also, the average benefit of split loads is found to range from 6 to 7% for most data sets. The heuristic was also tested on a real world example from the trucking industry. These tests reveal the benefit of both using split loads and allowing fleet sharing. The benefit for split loads is not as significant as with the random data, and the various business rules added for this case are tested to find those that have the most impact. It is found that an additional cost for every stop the vehicle makes strictly limits the potential for benefit from split loads. Finally, we present a simplified version of the PDPSL in which all origins are visited prior to any destination on a route, generalizing structural results from the Split Delivery Vehicle Routing Problem for this problem.

In this study we discuss the Vehicle Routing Problem with multiple use of vehicles (VRPM). In this variant of the routing problem the vehicles may replenish at any time at the depot. We present a detailed review of existing literature and propose two mathematical models to solve the VRPM. For these two models and their several variants we provide computational results based on the test problems taken from the literature. We also discuss a case study in which we are simultaneously dealing with side constraints such as time windows, working hour limits, backhaul customers and a heterogeneous vehicle fleet.

The transportation phase of solid waste management is highly critical as it may constitute approximately 60 to 75 percent of the total cost. Therefore, even a small amount of improvement in the collection operation can result in a significant saving in the overall cost. Despite the fact that there exist a considerable amount of studies on Vehicle Routing Problem (VRP), a vast majority of the existing studies are not integrated with GIS and hence they do not consider the path constraints of real road networks for waste collection such as one-way roads and U-Turns. This study involves the development of computer software that optimizes the waste collection routes for solid waste transportation considering the path constraints and road gradients. In this study, two different routing models are proposed. The aim of the first model is to minimize the total distance travelled whereas that of the second model is to minimize the total fuel consumption that depends on the loading conditions of the truck and the road gradient. A comparison is made between these two approaches. It is expected that the two approaches generate routes having different characteristics. The obtained results are satisfactory. The distance optimization model generates routes that are shorter in length whereas the fuel consumption optimization model generates routes that are slightly higher in length but provides waste collection on steeply inclined roads with lower truck load. The resultant routes are demonstrated on a 3D terrain view.

This study aims to improve transportation held between six auction centers, Inter-Auction Transportation, of FloraHolland. FloraHolland serves ninety eight percent of the Dutch market and is the largest auction in floriculture industry. The company wants to give the best sale opportunities with the costs as low as possible and this is the main initiative of this study. In this line of thought, FloraHolland wants to have a improvement on its current routing and scheduling mechanism. Exact models do not work due to the complexity and the size of the problem. Therefore, we developed a two-stage approach specific to this study. With this approach, we split exact approach into two, a mathematical model followed by a heuristic. In the exact approach, trucks are routed and scheduled at the same time. On the other hand, our solution approach first determines most efficient routes to be followed with Cycle Assignment Model and then, with Scheduling Heuristic, trucks are assigned to the routes, so within day transportation is planned in detail. Overall, each stage of this approach works in harmony and brings good solutions in a short CPU time.

The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions. / text

We analyze spatio-temporal routing under various constraints specific to multi-robot applications. Spatio-temporal routing requires multiple robots to visit spatial locations at specified time instants, while optimizing certain criteria like the total distance traveled, or the total energy consumed. Such a spatio-temporal concept is intuitively demonstrable through music (e.g. a musician routes multiple fingers to play a series of notes on an instrument at specified time instants). As such, we showcase much of our work on routing through this medium. Particular to robotic applications, we analyze constraints like maximum velocities that the robots cannot exceed, and information-exchange networks that must remain connected. Furthermore, we consider a notion of heterogeneity where robots and spatial locations are associated with multiple skills, and a robot can visit a location only if it has at least one skill in common with the skill set of that location. To extend the scope of our work, we analyze spatio-temporal routing in the context of a distributed framework, and a dynamic environment.

This thesis addresses the problem of motion planning for autonomous robots, given a map and an estimate of the robot pose within it. The motion planning problem for a mobile robot can be defined as computing a trajectory in an environment from one pose to another while avoiding obstacles and optimizing some objective such as path length or travel time, subject to constraints like vehicle dynamics limitations. More complex planning problems such as multi-robot planning or complete coverage of an area can also be defined within a similar optimization structure. The computational complexity of path planning presents a considerable challenge for real-time execution with limited resources and various methods of simplifying the problem formulation by discretizing the solution space are grouped under the class of discrete planning methods. The approach suggests representing the environment as a roadmap graph and formulating shortest path problems to compute optimal robot trajectories on it. This thesis presents two main contributions under the framework of discrete planning. The first contribution addresses complete coverage of an unknown environment by a single omnidirectional ground rover. The 2D occupancy grid map of the environment is first converted into a polygonal representation and decomposed into a set of convex sectors. Second, a coverage path is computed through the sectors using a hierarchical inter-sector and intra-sector optimization structure. It should be noted that both convex decomposition and optimal sector ordering are known NP-hard problems, which are solved using a greedy cut approximation algorithm and Travelling Salesman Problem (TSP) heuristics, respectively. The second contribution presents multi-robot path-planning strategies for recharging autonomous robots performing a persistent task. The work considers the case of surveillance missions performed by a team of Unmanned Aerial Vehicles (UAVs). The goal is to plan minimum cost paths for a separate team of dedicated charging robots such that they rendezvous with and recharge all the UAVs as needed. To this end, planar UAV trajectories are discretized into sets of charging locations and a partitioned directed acyclic graph subject to timing constraints is defined over them. Solutions consist of paths through the graph for each of the charging robots. The rendezvous planning problem for a single recharge cycle is formulated as a Mixed Integer Linear Program (MILP), and an algorithmic approach, using a transformation to the TSP, is presented as a scalable heuristic alternative to the MILP. The solution is then extended to longer planning horizons using both a receding horizon and an optimal fixed horizon strategy. Simulation results are presented for both contributions, which demonstrate solution quality and performance of the presented algorithms.

There is an increasing interest in sustainability and a growing debate about environmental policy measures aiming at the reduction of green house gas emissions across di erent economic sectors worldwide. The transportation sector is one major greenhouse gas emitter which is heavily regulated to reduce its dependance on oil. These regulations along with the growing customer awareness about global warming has led vehicle manufacturers to seek di erent technologies to improve vehicle e ciencies and reduce the green house gases emissions while at the same time meeting customer's expectation of mobility and exibility. Plug-in hybrid electric vehicles (PHEV) is one major promising solution for a smooth transition from oil dependent transportation sector to a clean electric based sector while not compromising the mobility and exibility of the drivers. In the medium term, plug-in hybrid electric vehicles (PHEV) can lead to signi cant reductions in transportation emissions. These vehicles are equipped with a larger battery than regular hybrid electric vehicles which can be recharged from the grid. For short trips, the PHEV can depend solely on the electric engine while for longer journeys the alternative fuel can assist the electric engine to achieve extended ranges. This is bene cial when the use pattern is mixed such that and short long distances needs to be covered. The plug-in hybrid electric vehicles are well-suited for logistics since they can avoid the possible disruption caused by charge depletion in case of all-electric vehicles with tight time schedules. The use of electricity and fuel gives rise to a new variant of the classical vehicle routing with time windows which we call the plug-in hybrid electric vehicle routing problem with time windows (PHEVRPTW). The objective of the PHEVRPTW is to minimize the routing costs of a eet of PHEVs by minimizing the time they run on gasoline while meeting the demand during the available time windows. As a result, the driver of the PHEV has two decisions to make at each node: (1) recharge the vehicle battery to achieve a longer range using electricity, or (2) continue to the next open time window with the option of using the alternative fuel. In this thesis, we present a mathematical formulation for the plug-in hybrid-electric vehicle routing problem with time windows. We solve this problem using a Lagrangian relaxation and we propose a new tabu search algorithm. We also present the rst results for the full adapted Solomon instances.