Huge amounts of resources are consumed daily by goods and personnel transportation. Using the available transportation resources as efficiently as possible is important for environmental considerations, and can be critical for the economic viability of the operator. Timeliness and customer service are other critical factors. So, finding a good plan for transportation is a very important problem.
Human planners are often good at finding reasonable efficient plans. However, when the cases become bigger and more complex, the number of possible routes becomes immense. While humans can still find reasonable plans using rules of thumb, automatic decision support systems can search through huge numbers of possible plans and very often find plans that are superior to the ones created by humans. Models and algorithms for solving these problems has been an area of research at SINTEF since the mid 1990ies.
The optimized management of a fleet of vehicles and other resources to meet a certain transportation demand is a critical challenge in many enterprises. Solving the Vehicle Routing Problem (VRP) is a key to efficient transportation management and supply-chain coordination. In broad terms, it deals with the optimal assignment of a set of transportation orders to a fleet of vehicles and the sequencing of stops for each vehicle. The objective is to minimize total transportation costs. Often, it is a combination of fleet acquisition / depreciation costs and transportation costs for the routing plan. The VRP has a large number of real-life applications and comes in many guises, depending on the type of operation, the time frame for decision making, the objective, and the types of constraint that must be adhered to. The VRP may be used for strategic decisions such as the long-term acquisition of vehicles or vessels, for tactical design of fixed routes, or the dynamic, minute to minute revision of routing plans.
Since 1995, the Group of Optimization at SINTEF has developed models and algorithms for many transportation optimization applications. In most projects, key results are prototypes or industrial strength software, either in the form of an optimization component or a decision support system. We have also assisted our clients in the development of requirements, specifications, and test cases for selection of existing transportation optimization tools. Our work has covered road based, maritime, airborne, and intermodal transportation. Among the results is Spider, a generic, industrial VRP solver that has been commercialized through a spin-off company and several other market channels. Spider is mainly used for road-based goods transportation, but it is also suitable for other types. A similar, generic solver for inventory routing (vehicle routing with inventory constraints) called Invent, is another major software result.
Most land based transportation problems have to deal with travel in a road network. Thus finding accurate travel times in the road network is an important subproblem. The shortest path problem has long been studied, but traditional algorithms are not sufficient for the problems encountered. One reason is that road networks can be very large, with several million nodes and edges. Another reason is the fact that travel times are not constant, but can vary e.g. with the time of day. These considerations have spurred a lot of research into the problem in recent years.
Research into shortest path algorithms at SINTEF has been incorporated in the Spider vehicle routing library. The software is also used in Spider Web, a standalone application for route finding.
2010
2009
2008
2007
Geir HasleChief Research ScientistSINTEF ICT, Department of Applied MathematicsAdjunct Professor, University of Jyväskylä, Finland
Oddvar KlosterResearch Scientist SINTEF ICT, Department of Applied Mathematics
