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 reasonably 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 a huge number 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.
Our competence in optimal route finding is also applied to air transportation in the SESAR project.
The internally financed Dynamo project (2011 with possible extension to 2012) aims at further development of highly efficient shortest path algorithms in intermodal transportation networks with time-varying travel speeds.
Total inland freight transport in the EU-27 was estimated to be close to 2.400.000 million tonne-kilometers in 2008; a little over three quarters (76.4 %) of this freight total was transported over roads. Savings of a few percent through optimization based planning tools give large benefits to economy and the environment.
The first transportation optimization application area studied at SINTEF was road-based goods transportation. Since 1995, SINTEF has developed models, algorithms, prototypes, and industrial software through various types of R&D projects partly financed by industry, the Research Council of Norway, the EU Commission, and SINTEF. The results, including the Spider industrial VRP solver, have been commercialized through several system and service providers.
Spider is integrated in the web-based distribution planning and management system of Distribution Innovation AS. 30 media product distribution companies in the Nordic countries utilize the solution, with a market share of 80% in Norway. Some 6100 carriers daily operate the routes that are revised and optimized using Spider.
In tactical fleet management, SINTEF has developed a component for optimized allocation of buses to contracts.
For the Nordic bus company Concordia, SINTEF has developed SINTOpt, a solver for combined shift and vehicle route planning. The implemented software resulted in a reduced number of shifts, less working hours, and a reduction of distance driven. The operational plans generated are robust and adhere to the drivers’ preferences.
Large amounts of goods are transported by ship. The high daily costs of running vessels means that even small gains in efficiency can mean huge economical savings.
Maritime inventory routing involves transporting goods by ship between ports where the goods are produced and consumed, while avoiding stockouts and storage overflows in the ports. The coordination of vessel routing and inventory managment and the coupling the arises between vessels that visit the same storage, make this a challenging problem. Compared to road-based problems, maritime problems have several characteristics that make this integration relevant. The quantities transported are large, both in terms of vessel capacity and storage capacity at production and consumption facilities. In addition, travel times between facilities are considerable. This leads to a problem where routing decisions has a large impact on the inventory levels and vice versa. Additional complications can arise from constraints such as draft limits, onboard stowage and cleaning requirements between different products.
Complex coordination, planning and scheduling challenges arise in the following areas of air transportation: Arrival management, departure management, surface management, and airport logistics, just to mention a few. The overall objective is to maximize throughput at the airports and minimize environmental impact, while maintaining safety and rules – both on ground and in the air.
SESAR (Single European Sky ATM Research - www.sesarju.eu) is the European air traffic control infrastructure modernisation programme. SESAR aims at developing the new generation air traffic management system capable of ensuring the safety and fluidity of air transport worldwide:
“By 2020, SESAR aims to creating the capability to handle a threefold increase in traffic in Europe, while improving safety by a factor of ten. The programme also seeks to reduce by 10 % the environmental impact per flight thanks to significant fuel reduction. The modernised air traffic management system in Europe should cut ATM-related expenses by half”.
Our group is participating in work packages 5, 10 and 12 of SESAR. In WP 10 – En-Route & Approach ATC Systems – we are working together with our partner SAAB to develop advanced departure management software. In WP 12 – Airport Systems – we are working with Park Air Systems to develop routing functionality for operational surface management.
Personnel scheduling—which has been subject to extensive studies over several decades—occurs in areas like airline crew, the retail sector, call centers, check-in counters, hospitals, public and private transportation, ambulance crew, etc.. It’s the process of creating a work schedule for personnel by matching staff to shifts for a given planning horizon while considering skills, competence, fairness, laws, and regulations. The output is a schedule of the working hours for the employees that also provides an overview of staff utilization and related expenses.
Producing a personnel schedule is a complex task: some organizations need staff every hour of every day and the demand for staff varies over time. In addition, the schedule must follow labor laws, union regulations, organizations' policies, and sometimes even consider employees preference. The task also involves multiple stakeholders (employer, employees, and customers), whose objectives need to be taken into consideration simultaneously when searching for the best schedule. The main focus of the employer might be efficient resource utilization at minimum cost, while an employee would like to see fair working patterns and the possibility to plan non-working time. For the customers, short waiting time and quality of service (personnel competence) might be the main concern.
We have built personnel scheduling engines for organizations since 2004. The scheduling engines are tailored for their specific hard constraints (labor laws, union regulations, etc.) and soft constraints (e.g. employees preference). We are currently working on systems for organizations in the transport and health domain.
2012
2011
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
