4 Presentations

• 
  10:30 AM - 11:00 AM

  The Departure Time and Speed Optimization Problem

  • Anna Franceschetti, presenter, Eindhoven University of Technology
  • Dorothée Honhon, Eindhoven University of Technology
  • Tom Van Woensel, Eindhoven University of Technology
  • Tolga Bektas, University of Southampton
  • Gilbert Laporte, HEC Montréal

  Given a fixed sequence of customer nodes and a single vehicle the Departure Time and Speed Optimization problem (DSOP) consists of optimizing departure times and travel speeds in a presence of traffic congestion, which at peak periods restricts the vehicle speed and significantly increases the fuel consumption. The objective is to minimize a total cost function comprising of fuel cost and driver wage. The travel time between two nodes is time-dependent and the traffic congestion is modeled using a two-level speed function where there is an initial period of congestion followed by a period of free-flow. This modeling framework is suitable for delivery planning problems which must be executed in the first half of a given day, e.g., starting from a peak-morning period where traffic congestion is expected, and following which it will dissipate. To each customer node corresponds a service time and a hard time window in which service must start. In case of an early arrival the vehicle is allowed to wait at a customer for the service to start. To account for the negative impact of traffic congestion we make use of the "idle waiting" strategy. Namely, we allow the vehicle to wait idly at certain locations after service is completed, in order to avoid driving in congestion and to reduce the cost of emissions. Building on some analytical properties of a single-arc instance we describe a recursive algorithm to solve the DSOP on a fixed sequence of nodes. We also show that the optimal solution can be found in polynomial time.

• 
  11:00 AM - 11:30 AM

  An Elementary Shortest Path Problem with Variable Service Start Times

  • Hande Küçükaydin, presenter, University of Liège, HEC Management School
  • Yasemin Arda, University of Liège, HEC Management School
  • Yves Crama, University of Liège, HEC Management School

  We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves a set of delivery and backhaul customers with a revenue and a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where a customer is either a delivery or a backhaul customer, but not both. Split deliveries and pick-ups are not allowed. In this problem, multiple trips are allowed so that the vehicle can be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. In other words, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the aim is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the routing costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices.
  In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, we present computational results.

• 
  11:30 AM - 12:00 PM

  A Time-Constrained Shortest Path Problem with Stochastic Costs

  • Martin Prillard, Université de Technologie de Troyes
  • Christophe Duhamel, presenter, LIMOS, Université Clermont-Ferrand II
  • Andréa Santos, ICD-LOSI, UTT, Troyes
  • Thibaut Vidal, CIRRELT, Université de Montréal & ICD-LOSI, Université de Technologie de Troyes

  Given a connected digraph G=(N,A) where N is the set of nodes and A is the set of arcs, we consider the problem of finding an optimal path from an origin node o to a destination node d. Each arc a is given a distance d_a and a speed limit l_a, L being the set of the legal speed limits. The cost of a path from o to d is separable on the arcs. It takes into account the travel duration and the fuel consumption. Both depend on the average speed chosen for the arc. Highway tolls are also considered.
  Besides, a maximal travel time T is set. It forces the vehicle to exceed the speed limit on some arcs, with the risk of being caught by radars. Two kinds of radars are used: static radars whose location is known and mobile radars randomly located on the graph. The amount of mobile radars is supposed to be known. The probability of being caught and the amount of the fine depend on the speed excess. Thus, the problem is to find a path from o to d and to set the speed on each arc such that the time limit is satisfied and the total cost (including fines) is minimized.
  After modeling the problem, we propose a dynamic programming approach. It extends the classic labeling algorithm used to solve the Elementary Shortest Path Problem with Resource Constraints since speeds have to be set during the label propagation. Numerical results are provided on some test instances. The impact on some label propagation strategies on both the CPU time and the quality of the results is shown.

• 
  12:00 PM - 12:30 PM

  Maritime Fleet Deployment with Speed Optimization

  • Kjetil Fagerholt, presenter, Norwegian University of Science and Technology
  • Henrik Andersson, Norwegian University of Science and Technology
  • Kirsti Hobbesland, Norwegian University of Science and Technology

  We consider a fleet deployment problem for a ship operator in the roll on-roll off segment of liner shipping dealing with the transportation of cars, trucks and other types of rolling material. Fleet deployment is a tactical decision with a planning horizon of typically 3 - 9 months. Given a heterogeneous fleet of ships and a number of voyages that the company must service, the problem is to assign a ship to each voyage in order to minimize the cost. We present a mathematical formulation for this planning problem that considers frequency requirements for voyages and demand between different geographical areas. We also treat sailing speeds of the ships on the individual voyages and the ballast sailing legs as decisions variables, where the non-linear relation between speed and fuel consumption is approximated with a piecewise linear function.

  To solve problems of real size, a rolling horizon heuristic is proposed. The principle of the heuristic is to solve the problem iteratively through the planning horizon. The planning horizon is partitioned into time periods, which each consist of two sections. The first section is the central section and the second is the forecasting section. During a given iteration, the planning problem for that time period is solved. The solution in the central section is then frozen and a new planning problem for the following time period is defined. In the new problem, the forecasting section of the previous iteration becomes the new central section. The algorithm continues until the solution for the whole planning horizon is frozen.

  The method has been tested on real data provided by a shipping company. The largest instances have more than 50 ships and 300 voyages, covering a nine month planning horizon. The tests show that the proposed method performs well and produces good solutions. The results also show that significantly better solutions are obtained when incorporating speed as decision variables in the fleet deployment planning.