by Jianyang Zhou, Jianyi Zhou, Jiande Zhou, Yann Courtet, Weiping Wu and Hua Ni
In modern logistics, multi-modal transport planning and vehicle routing represent two major problems. Within a supply chain, the first determines how to forward freight between different regions, while the second plans the local fleet of vehicles, both in order to minimize transport costs. These problems are significant for third- and/or fourth-party logistics. In practice, complex transport conditions such as on-time delivery, capacity (quantity/volume/weight), work regulation (time/break/makespan), transport mode, security and coupling constraints may lead to computational challenges for the optimization engine.
POEM (Programming in Operational and Expressive Models) is a planning and scheduling solution-building system. The POEM Solution Builder is composed of a core technology and an auxiliary one: Natural Constraint Language (NCL) and Visual Script.
NCL is a descriptive language for business modelling and problem-solving based on conventional mathematical logic. Visual Script in POEM is a GUI script that supports solution visualisation (basic graphics/map/time) and interaction management. In an all-in-one style, POEM embeds OR algorithms, logic, heuristic rules and GUI in a single system to offer users a cost-efficient choice with benefits in training, management, development, deployment and maintenance.
As a development tool, POEM narrows the gap between developers and end users thanks to its visual modelling and debugging interface. Figure 1 shows the visual nature of POEM modelling and diagnosing.
POEM is also designed to be an application platform. In order that a single solver can support a variety of applications, POEM advocates the development of modular solutions for different businesses. For instance, production planning and scheduling, distribution optimisation and personnel planning can all be performed on the POEM platform. To illustrate this point, two POEM solutions for logistics planning are presented below.
Multi-Modal Transport Planning
Multi-Modal Transport Planning (MMTP) involves planning the flow of goods and services along a supply chain. For example, fourth-party logistics requires that transport costs be optimized for on-time delivery of goods from vendors to customers. Transport occurs through multi-modal trade lanes, such as air, rail, road and shipping, with each of these incurring a different cost. In addition, a feasible transport plan must simultaneously satisfy constraints such as vendor (production) capacity, vehicle (route) capacity, transportation schedules (eg an air company may offer several flights per day), and cross docking and service times. Everyday examples of MMTP applications include mail/parcel delivery, freight forwarding and so forth.
Compared to vehicle routing, MMTP is a capacitated freight-routing problem. Each route may have several shifts per day; for example, air transportation may have one flight at 9:00am and a second at 2:00pm each day, with each flight having a limited capacity (quantity/volume/weight). For each customer order, freight routing determines an itinerary from origin to destination that identifies each form of transport used and the overall schedule, and satisfies all the delivery constraints. See Figure 2 for an illustration of multi-modal transport plans.
Vehicle Routing and Scheduling
Vehicle routing and scheduling is the optimisation of delivery routes, which may be subject to constraints as diverse as vehicle capacity (quantity/volume/ weight), work regulations (time/break/ makespan), time windows (eg a customer may prefer a morning to an afternoon delivery), distance, route accessibility and coupling (ie certain customers should or should not be serviced by the same truck). There may also be multiple objectives: for example, to minimize the number of vehicles, work-time, makespan and mileage.
In real life, vehicle loading can be a significant concern for logistics companies: trucks are expected to be fully loaded for most of their routes (see the statistics in Figure 3: almost all the trucks are well loaded). This makes it necessary to first work out the truck plans so as to balance truck loading and take into account time constraints. After truck planning, the system computes the best route and schedule for each trip subject to work regulations and delivery constraints.
Re-Planning and Re-Scheduling
For practical solutions, planning flexibility is of great importance. Circumstances will arise where it is necessary to modify transport modes, delivery schedules, or to shift customer orders from one route to another. In other words, operators may need to intervene in the system's planning solution based on their expertise or experience. For both freight and vehicle routing, the system allows flexible re-planning and re-scheduling to meet the requirements of customer changes and interaction.
This research has been undertaken by ENGINEST. The company is a spin-off from INRIA and is working in the area of logic programming and operations research, with particular interest in resource optimisation for logistics, manufacturing, and human resources.
The 'POEM Modular Solutions' project was started in 2000, and is being extended to better deal with industrial applications in different domains. Future work will look into more powerful OR algorithms and more user-friendly interfaces for the modular solutions. Cooperation with renowned laboratories in these areas is expected.
Tel: +33 3 83 55 12 99