One of the most involved problems in Operations Research is to find the shortest path connecting a set of given points. In the classic Traveling Salesman Problem, a salesman has to visit each of a set number of locations (may be shops, cities or countries and a combination of these) and then return. Similarly, in a Vehicle Routing Problem, a fleet of vehicles has to make deliveries or pick-ups from a set of customer locations. The objective in either case could be to create a schedule that minimizes the total cost of travel. Such real world problems are subject to many conflicting constraints making them very complex to solve.

Travel Route Optimization (TRO) is one way by which such problems may be solved. Given a set of locations to be visited, TRO can generate a route that results in the optimization of a business objective, subject to a set of constraints.

Objectives in a TRO problem may include one or a combination of

• minimizing total cost of travel
• minimizing time taken to visit all locations
• minimizing distance traveled

Constraints in a TRO problem depend upon the specific business situation. For instance, the Medical Representatives are supposed to visit the doctors only during specified visiting hours. The constraints in a TRO problem may include one or more of

• number of times a particular location is to be visited
• dates/time of visiting a particular location
• time between consecutive visits to a location
• maximum travel time available
• capacity of vehicle to be routed for pickups/deliveries
• maximum number of locations to be visited in one trip
• vehicle availability

Applications where TRO is/may be used include

• scheduling sales force personnel for customer visits
• routing of trucks for delivery of goods from warehouses to depots
• scheduling of stacker cranes in warehouses
• routing of trucks for parcel post pickup
• door-delivery of meals by pizza and other food chains
• scheduling of service calls at cable firms
• routing of an automatic drill to make holes on a circuit board
• routing of school bus to pick up the children in a school district

TRO solutions can be interfaced with GPS/GIS systems for adaptive and real time scheduling.

Requirements of a good TRO solution include

• Clearly defined business objective(s)
• Identification of problem and constraints
• Clean, standardized data
• Selection of appropriate heuristic(s)
• Powerful What-if analysis
• User-friendly interface
• Effective presentation and visualization of results
  

Modeling solutions based on optimization techniques like TRO have been gaining wide acceptance to support decision making in today's businesses. However, effective modeling solutions deliver much more than a powerful optimization engine.

Formal modeling of complex decision making tasks creates multiple advantages. Check out our next issue 'Why Model' for the benefits of formally modeled solutions.

© 2000-10 DecisionCraft Inc.