Improved solutions to dynamic and stochastic maritime pick-up and delivery problems using local search.

Heuristics for stochastic and dynamic vehicle routing problems are often kept relatively simple, in part due to the high computational burden resulting from having to consider stochastic information in some form. In this work, three existing heuristics are extended by three different local search variations: a first improvement descent using stochastic information, a tabu search using stochastic information when updating the incumbent solution, and a tabu search using stochastic information when selecting moves based on a list of moves determined through a proxy evaluation. In particular, the three local search variations are designed to utilize stochastic information in the form of sampled scenarios. The results indicate that adding local search using stochastic information to the existing heuristics can further reduce operating costs for shipping companies by 0.5–2 %. While the existing heuristics could produce structurally different solutions even when using similar stochastic information in the search, the appended local search methods seem able to make the final solutions more similar in structure.

Determining departure times in dynamic and stochastic maritime routing and scheduling problem

In maritime transportation, decisions are made in a dynamic setting where many aspects of the future are uncertain. However, most academic literature on maritime transportation considers static and deterministic routing and scheduling problems. This work addresses a gap in the literature on dynamic and stochastic maritime routing and scheduling problems, by focusing on the scheduling of departure times. Five simple strategies for setting departure times are considered, as well as a more advanced strategy which involves solving a mixed integer mathematical programming problem. The latter strategy is significantly better than the other methods, while adding only a small computational effort.

A Hardware Task-Graph Scheduler for Reconfigurable Multi-tasking Systems

Reconfigurable hardware can be used to build a multitasking system where tasks are assigned to HW resources at run-time according to the requirements of the running applications. These tasks are frequently represented as direct acyclic graphs and their execution is typically controlled by an embedded processor that schedules the graph execution. In order to improve the efficiency of the system, the scheduler can apply prefetch and reuse techniques that can greatly reduce the reconfiguration latencies. For an embedded processor all these computations represent a heavy computational load that can significantly reduce the system performance. To overcome this problem we have implemented a HW scheduler using reconfigurable resources. In addition we have implemented both prefetch and replacement techniques that obtain as good results as previous complex SW approaches, while demanding just a few clock cycles to carry out the computations. We consider that the HW cost of the system (in our experiments 3% of a Virtex-II PRO xc2vp30 FPGA) is affordable taking into account the great efficiency of the techniques applied to hide the reconfiguration latency and the negligible run-time penalty introduced by the scheduler computations.