The freight transportation sector accounts for a major percentage of the global economy. Companies in this sector face a major challenge when planning their operations: on a regular basis, they need to decide which truck serves which customer and in which order. For example, every day, the Belgian Post Office develops an operational plan for it fleet of vehicles to pick-up and deliver all the packages in the most efficient way possible. These kinds of problems are known as Vehicle Routing Problems and have been widely studied by the OR community.
In most of the cases, Vehicle Routing Problems aim to find the set of routes that the vehicles should traverse in order to minimize the total transportation cost. However, in many real-life cases, there are additional constraints that should be taken into account. For instance:
- Companies that transport valuable goods usually need to follow very strict policies imposed by insurance companies. For example, they might have specific limits on the amount of goods they can transport, the total distance they can travel or another measure of the risk they can take.
- Many companies divide their distribution areas in different zones that need to be served. These companies not only need to determine the routes the vehicles should follow, but which vehicles are assigned to which service areas.
- Several organizations transport people instead of material goods. For example, ambulances are required to transport patients to hospitals, and school buses are required to transport children to schools. In these cases, the transportation cost is not as important as other service measures. For instance, how fast critical patients arrive to their nearest hospital or the time children should wait for their bus.