Software Review
A.MAZE Routes & Zones
Transportation management system offers fleet scheduling solutions for large organizations
By Louis Leclerc and Steve Thiboutot
There are a number of challenges and barriers to adoption of routing and scheduling technology. Most private fleets still manually route their individual trucks per fixed-regions or skeleton routes, or rely on legacy systems and drag-and-drop manipulations. There is strong resistance to change. Adoption rates should accelerate as resistance to change is overcome by the evidence of results driven by accurate modeling environments, clear demonstration of the scalability and deployability of newer software architectures, and proven return on investment and efficiency gains demonstrated by initial implementations. Fleet optimization should be adopted because it is a paradigm shifting technology that will increase efficiency, and, more importantly, save money.
A.MAZE Routes and Zones created by GEOCOM are part of a suite of new tools for fleet routing and scheduling, territory design optimization, and tracking and messaging. This software solution is built on a distributed component architecture, and is designed specifically to tackle large and complex fleet optimization in the last mile of the supply-chain (for example: less-than-truckload and local pickup and delivery where street-level routing and modeling of complex operations constraints are a must). The software features a multi-user, multi-vehicle routing and scheduling environment, providing visibility between dispatchers and allowing plans to be optimized across geographic boundaries.
One of the innovative differences of the approach is that it employs distributed network components system architecture. The network components allow the architecture to be scaled to large problems and facilitate ease of integration. This technology infrastructure, when combined with complex constraint-modeling, genetic algorithms and high quality maps, enables companies with large fleets to implement, automate and reap value from optimizing their operations.
The software suite also has a wireless component built in. A wireless-gateway communicating with mobile PDAs provides real-time feedback and response (RTFR) for tracking and status notification enabling immediate response actions in a multi-dispatcher or automated environment. As an example, if a vehicle is running late, the dispatcher/system is notified so orders of that trip can be automatically rescheduled. The trip can be re-organized, coordinated and then the new changes communicated back to drivers.
A.MAZE Routes relies on a mixed application of genetic algorithm and modified simulated annealing that each tackle specific parts of the large and complex problem of searching quickly for a very good (as close-to-optimal) solution given a limited search time, allocating jobs to transportation resources to form trips, and building valid sequences for these trips while simulating all defined constraints. The ultimate goal is to maximize efficiency of each trip therefore generating fewer trips for the entire problem space and minimizing global costs.
Problem Definition and Environment
The basic model for fleet scheduling requires a given set of locations to visit and a fleet of resources to visit them. Increasingly complex constraints must be layered and modeled to create a real-life solution:
- The locations to be serviced may require specific services to render (simple pickup or deliveries, all the way to complex processes requiring qualifications and dependencies between jobs and vehicles);
- specific physical requirements for volumes/weights or any other capacity,
- duration that may vary according to the workload (ex: number of cases or liters to deliver),
- "rate of work" and optional setup-time may be location-based, and
- multiple hard time-windows constraints that reflect customer requirements.
- The fleet used to service these locations is composed of several vehicles (maybe hundreds), that must be modeled as a set of finite-capacity resources;
- to which jobs will be allocated,
- for which each vehicle will be assigned a set of physical properties and limitations,
- service-qualifications that will have an impact on their ability to be allocated certain jobs, and
- working-structure (ability to handle drop-and-hook, variable start-time and break-structures based on union contracts, for example).
- Finally, external factors must also be modeled, such as the existence of time and/or service-dependant depots or re-fueling stations;
- that may or may not handle the products transported by the specific vehicles, or
- only be available during certain time windows.
presentations/ROUTE2000-daganzo.PDF, Page 29, refer to possible productivity gains as high as 25 percent in fleet reductions. )
For Tanguay's Logistics group, it became evident that, in order to automate our process of scheduling delivery activities, we had to:
- remove the manual guesswork of dragging-and-dropping;
- help the dispatchers with a tool that builds routes taking into account constraints modeling;
- raise the level of accuracy of routing in order to improve the acceptance factor by the drivers, which is important to respect when introducing new technology and business processes;
- roll-out a solution that could automate the dispatching and routing process, scale to the size and growth-path of our organization in order to enable our dispatchers to collaborate across territories and fleets to improve the efficiency of the operations, and ultimately lower costs and better serve our customers; and
- demonstrate a sizeable optimization that could systematically improve our service level, which is the main driver at Tanguay.
Scalable Architecture
At Tanguay, the requirements have been driven by the business challenges. From an environment with seven sales points, four warehouses, an average of 750 delivery points daily (up to peaks of 1,000+) and dispatchers physically separated, to the initial requirements for an excellent mapping coverage (the entire Quebec territory) and an effective planning engine, we quickly added scalability, deployment and maintenance concerns.
Figure 1: The A.MAZE services-based architecture emphasizes flexibility, scalability and deployability.
To support a collaborative fleet optimization approach, a distributed and scalable architecture was required. Due to the potential complexity of our largely constrained model, the software was to be designed so that hardware was not a limitation. GEOCOM uses a distributed component architecture based on the widely used TCP/IP protocol and the newest concept of network services, enabling specific services (such as cartography servers, calculation servers, database servers) to be replicated and adapted to meet workload as the automated dispatching process and usage will dictate. It uses standard enterprise RDBMS that allows Tanguay to create one link between its central order-entry database and A.MAZE Routes.
It took Tanguay's IT department three days to design the interface between its Order Management System (based on Progress) and the A.MAZE Routes system (our implementation uses Oracle), and an additional eight days to improve our in-house system to reap the benefits of a better modeling of order service duration that the routing and scheduling package would allow us to model. The basic information to be shared between the two platforms was well defined and structured ahead of time, and the engineer from GEOCOM that supervised our integration process was well-versed in the application and definitely eased the process of interface building.
In terms of architecture for integration, deployment and maintenance, A.MAZE Routes is well-presented and well-designed. It is quite easy for users to learn because of an intuitive user-interface, and a clever way of literally navigating through the large amount of information, as well as running searches and reporting.
In comparison, traditional workstation-based architectures are difficult to integrate for running routing and scheduling as background processes within a broader system's architecture. Stand-alone PC-based software have sometimes been repackaged with a thin-client delivery-layer in order to distribute the data-entry portion of the software functionality, and enable database centralization to ease connectivity with the master order entry systems. Although this thin-wrapper (Citrix Metaframe or Terminal Server) helps in the centralization and maintenance efforts, there is still a one-to-one relationship between the problem to be solved and the processing capacity of the solve-engine server which will eventually become a bottleneck as the problem size grows.
Distributed-component architectures have the ability to solve the problem of scalability and ease the distribution of complex components such as GIS-based graphical user interfaces and geocoding, and routing and sequencing engines. This new approach to architecture that the A.MAZE Suite employs is important to large corporations, because:
1. Every piece of the software is a deployable component. This means:
- only the presentation layer of the software needs to be deployed on clients;
- all mapping, optimization and data services may be deployed and centralized in data centers according to corporations' needs; and
- the application will scale to much larger environments because it may be load-balanced across a large number of servers and CPUs.
2. Secondary products (for example, A.MAZE Zones) revolve around the same integrated services using the same database, the same cartography and the same optimization mechanism. For Tanguay that meant no internal effort to integrate the two products, the reduction of the implementation time, the reduction of training efforts and costs on a new product and new GUI interface, the ease of playing with what-if scenarios, as well as the flexibility to integrate those scenarios into our daily routing operations. This way of exploiting the same components for different usage also enabled the efficient collaboration between different players/departments involved in the routing and dispatching environment. Yet, it clearly simplified the IT department's task when deploying and supporting users located at various sites, because all services can be maintained from a same central IT location.
3. All components of the application are written in the same programming language using a consistent development process.
4. Having been developed over the last 18 months, all of the components are contemporary. There is no legacy architecture, and the development team has not changed.
User Interface: The application follows the look and feel of traditional Windows products. The software offers all the visual routing and dispatching aspects a user expects. There is a graphical dispatcher's console where maps and Gantt charts are displayed. The resource and constraint-modeling environment is presented in the graphical user interface as simple tables with a clever and effective drill-down/drill-across data navigation process. Also, a very intuitive address-correction utility is provided to help the user "purify" the geocoding data, in case of bad spelling coming from external order entry systems for example.
Figure 2: With the look and feel of traditional Windows products, user interface offers expected visual routing and dispatching aspects.
Automation: From the very beginning of the selection process, Tanguay felt that automation was a major differentiator between the A.MAZE application and several of the competing software packages. A.MAZE was designed to automate the process of routing and scheduling, which is a rather refreshing message when compared to the traditional world of drag-and-drop applications where the software will take a first cut at the problem, and let users figure out better ways to improve it.
Tanguay's operating mode presents various constraints that absolutely have to be taken into account when executing the routing and scheduling process. As an example, Tanguay runs two different fleets, one for the standard furniture delivery, and one for the more luxurious brands sold by a different branch called Signature. For all orders from the Signature stores, only the trucks with the Signature's logo can be assigned for deliveries. On the other hand, standard orders typically use the standard Tanguay trucks, but it may be allowed to use the Signature truck if optimization can be found during the automated scheduling process.
In addition, a large portion of our orders get assigned one or more specific time-windows to be met, usually set at customer's requirements. This is what sets Tanguay apart from its competition — a very high standard of service level. Unfortunately, this may hamper the overall productivity of our fleet, because first, it is an extremely tough problem to solve and definitely can not be solved manually as well as a fully automated optimization solve engine. Second, this very constrained mode of operating the delivery process requires a much more flexible way of routing that is just not compatible anymore with fixed regions allocations (or skeleton routes).
Finally, the furniture business has to deal with a lot of variations in volumes to be handled, and it's the marketplace that dictates what you will deliver, not statistics. In order to automate the routing and scheduling process, Tanguay needed a software solution that could simultaneously route and solve the many constraints around our delivery process.
Geocoding: Geocoding is the process of looking at a textual string of words and characters, and figuring out where, in term of Latitude and Longitude a particular address is, no matter how accurate (or inaccurate) this data is. Misspelled street names, wrong city name, no zip/postal code or wrong zip/postal code, these are all examples of what a thorough geocoding engine has to deal with. Interfaced to order entry systems, A.MAZE Routes automatically handles the geocoding process of addresses.
Real-Time Data Integration and Reporting: A nice feature, and another differentiator from traditional packages, is the software's ability to receive, in real-time, new orders from external systems, and optionally, automatically schedule them. The software either allows for the dispatchers to practice the allocation themselves, or automatically allocates them, based on territories designed by zones or fuzzy-zones, "best-fits" the new jobs to any available vehicle, while making sure the allocation will respect all availability and qualification constraints, delivering on the promises of on-line real-time routing and scheduling.
After simultaneously running the routing and scheduling optimization process, A.MAZE Routes allows to transfer sequences of orders and related information to each specific mobile PDA. It also receives updates from the mobile devices as statuses of work orders are changed from the field. Integrating the wireless mobile devices delivers on automation, which has become essential now that logistics and distribution are finally becoming integrated into the main Enterprise systems.
Because of wireless status reporting, and its use of standard DBMS, A.MAZE Routes enables data-collection and the creation of statistical reporting.
Routing and Scheduling Engine
The solution engine of the A.MAZE Suite is one of the major differentiators of this approach from traditional applications. It uses two meta-heuristics that improve solutions over time (Genetic algorithms [GA] and Modified Simulated annealing) in conjunction with an adaptive rule-based system which can handle complex constraints whose application may vary with the context (i.e., breaks that vary according to trip duration; returns to different depots according to the loading of the vehicles which varies according to the trip sequence).
GA derives its name from the process of creating populations of solutions in order to search for incremental improvements. It is especially well-suited in environments where the search environment is so large/dynamic that simple heuristic methods would find one possible solution out of a large number of other solutions, therefore missing out on the real optimization potential. As an example, the sequencing problem is a permutation one. Five stops will lead to 120 possible sequences; two hundred stops will lead to 7.8374 possible solutions. The sheer size of these problems has led most vendors to adopt strong problem reduction techniques, and focus on local optimization based on skeleton routes instead of tackling the much larger fleet sequencing optimization problem.
Other approaches (such as construction and improvement heuristics) have been hard to use because of the complexity of modeling the dynamic constraints of real-life environments. An example would be the dynamic loading of trucks for an entire fleet; the sequence of delivery dictates what to load in order to maximize the efficiency of the trucks (ex: max. deliveries per hour), but the required volumes will in reverse constrain the sequence that we want to build (the chicken and the egg problem).
A.MAZE Routes relies on standard job sequencing simulation, laying out stops in sequence and calculating the resulting scheduling of each sequence. The constraint-based engine starts from randomly generated sequences, avoiding all initial "seed" assumptions. From there, it generates alternate possibilities through mutations and crossovers, constantly looking to optimize while evaluating each one for constraint violations, and taking only the viable options for further randomizing to the next level of search. This is repeated as many times as selected and each time, only the improved solutions survive.
GA and simulated annealing by themselves can not solely allow for scalability, but in conjunction with the proper software architecture and well designed supporting data structure (for example, simply building a sufficient distance and duration matrix between nearest neighbors for a large dataset of several thousands of points, is a major task by itself), it enables large problem spaces to be dynamically segmented. This enables the "search" for solutions to be allocated to a scaleable distributed-component network of routing, sequencing and calculation (optimization) services, and gradually improved through subsequent smaller, but very quick, steps over an allocated period of time.
Because of the scalability of this architecture, it now becomes possible to address the problems at the fleet level, simultaneously simulating sequences and considering each vehicle's capacity and qualified services, time-windows and all key constraints based on more than 15 different street-level routing parameters such as turn restrictions, one-ways, low bridges, no truck streets, toll roads, medians, etc. (Note: Some packages do not use GIS data for distance calculation within routing. This can cause serious inaccuracies for drivers and can result in routes that cannot be run as planned.)
The A.MAZE Routes and Zones Suite provides the above routing features and uses the same meta-heuristics solution approach to provide additional functions such as advanced zone design (constrained, overlapped [dynamic routing] and non-overlapped [simple skeleton routing]), fleet sizing, dynamic sourcing, source follow-up and drop-and hook in one standard application.
Implementation
A.MAZE Routes and Zones are standard Windows products, and installation is straightforward. The product is supplied on a DVD-ROM, and the GEOCOM engineers used the installation "wizard" to get A.MAZE Routes up and running without any difficulties. The wizard follows Windows conventions for file locations. Specifically, in the case of Tanguay Furniture, the installation took two days to configure for eight simultaneous users, and eight more days to build the interface to the Tanguay order-entry system, directly tying sales to the delivery routing and scheduling process.
The software uses the standard multiple-document interface typical of Windows products, and allows users to look at different aspects and scenarios of the same simulation model in different windows or different PCs. It also allows multiple models to be simultaneously open, which is useful for engineering simulations.
Another key difference of this product suite is that, compared to desktop-based applications that have to be implemented and upgraded on every desktop, A.MAZE Routes and Zones are installed on one or many servers (as required by the mapping, geocoding and routing and scheduling workload), and only the presentation layer is required for each client — no additional software is required by the client. Importantly, there is no requirement to install large mapping data files onto each client PC, and update them as the street network evolves. This removes a requirement that contributed to routing and scheduling project failures in the past. A.MAZE Routes and Zones implementation efforts and upgrade activities are performed centrally, and most of the upgrade activity is done on the central server, easing deployability and maintenance efforts.
The software comes bundled with required maps and some standard reports. The system also enables users to develop their own reports using Crystal Reports.
Help Manual
A.MAZE Routes and Zones come with a well-written online manual. It should be easy for most users to understand it — even those with little exposure to computers and simulations — thus reducing training and support requirements. This includes a step-by-step guide on how to build the models from scratch, as well as some discussions of the modeling decisions made.
Summary
A.MAZE Routes still has a few rough edges. Server installation is not for the faint-hearted and should be left to GEOCOM field engineers, but at least, all the major components of the architecture (ex: load balancing) rely on standard operating systems features, and are well used throughout the industry.
The product will complain if data coming from the order entry systems is not accurate enough to enable proper geocoding (placing a dot at an exact location on the map), and although there is no such thing as a perfect geocoder (as street-level data is not a totally completed job anywhere, even in America and Europe — and it evolves every day), the address-corrector feature makes the remaining task of fixing three to five percent of addresses less cumbersome.
The software has a nice look and feel to it, making it easy to use for simulation projects and full-automation of the routing and scheduling process. The package shines by its ability to automate the process of building cost-efficient routes that respect accurately all constraints modeled in our business process (weights, volumes, strict time windows, different services per order and per truck) and definitely delivers on the optimization side. Tanguay witnessed an 11 percent increase in resource efficiency and a reduction of more than 60 percent of the dispatching workforce.
On the whole, this is a good fleet scheduling solution, suitable for larger organizations and more complex problems, especially when compared with other traditional software products. It is also quite useful for educational purposes since simulations may be set up rapidly and easily. For larger, heavy-duty uses, our view is that A.MAZE Routes is very suitable from a number of viewpoints:
- It provides ways of importing custom data from or to files or DBMS.
- The optimization process is fast and very accurate in constraints modeling with respect to other software packages we have seen on the market.
- The architecture simply makes it scalable and easily upgradable, especially since there is no need for a deployment of mapping data to the client.
|
|
Louis Leclerc is the director of logistics and Steve Thiboutot is the IT manager at Tanguay Furniture, the leading furniture company in Eastern Canada.
OR/MS Today copyright © 2003 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2003 by Lionheart Publishing, Inc. All rights reserved.