Logistics optimization

We are developing optimization software tools for decision support in logistics. These are the Vehicle Routing Planner (VRP), Modal-Shift Transportation Planner (MSTP), Warehouse Location Planner (WLP), and Warehouse Location and Transportation Planner (WLTP). By using simulation and newly developed heuristics, these software tools can find excellent solutions quickly.

1. Vehicle Routing Planner (VRP)

VRP is an operational decision support tool for geographically distributed businesses, such as the delivery of goods from a depot (or multiple depots) to customers by a fleet of trucks. We can use VRP to find the optimal routes for delivery trucks on the road network that minimize the number of trucks required, under constraints on capacity, time, and customer demand. VRP was developed on the basis of heuristics for the traveling salesman problem (TSP), which were developed mainly for solving problems in manufacturing, such as the printed-circuit-board-drilling problem. We succeeded in transforming the vehicle routing problem into the TSP, and applied our expertise in the TSP to vehicle routing. We are now developing prototype solutions for several customers.

2. Modal-Shift Transportation Planner (MSTP)

When optimizing wide area logistics such as for a nationalwide or worldwide scale, we need to optimize inter-facility transportation in addition to regional optimization, which is the problem solved by VRP. For inter-facility transportation, the transportation modes (carriers) expand from trucks and trains to ships and airplanes, and the best choice of the modes, i.e., modal shift, has a great impact on the total cost. MSTP uses an algorithm based on the steepest descent method and can find an excellent transportation schedule quickly.

3. Warehouse Location Planner (WLP)

WLP is a strategic decision support tool for geographically distributed business tasks, such as delivery of goods from several warehouses to a large number of customers. It can find the optimal number and locations of warehouses to minimize the total cost, which consists of transportation costs and warehouse fixed costs, while satisfying customer requirements. In 1996, we applied WLP to a very large warehouse relocation problem experienced by a manufacturing company in Japan, and found a solution that achieved a 10% cost reduction. Significant data, such as transportation costs and warehouse fixed costs can be simulated by using digital road maps from car-navigation systems.

4. Warehouse Location and Transportation Planner (WLTP)

We need to calculate distances among multiple points very often when using the above logistics optimization tools. Therefore, we developed efficient algorithms to find the set of shortest paths among multiple points. These technologies are implemented in "Super-IFMAP" - a geographic information system program by IBM Japan. We also developed a TSP (Traveling Salesman Problem) solver for non-geometric spaces.

• Journal papers
  • H. Okano, S. Misono, and K. Iwano, "New TSP Construction Heuristics and Their Relationships to the 2-Opt", Journal of Heuristics, 5, pp.71-88, 1999.
  • N. Park, H. Okano, H. Imai, "A Path-Exchange-Type Local Search Algorithm for Vehicle Routing and its Efficient Search Strategy", Journal of ORSJ, 43, pp.197-208, 2000.
  • K. Hidaka and H. Okano, "An Approximation Algorithm for a Large-Scale Facility Location Problem", Algorithmica, in press.
• International conference
  • K. Hidaka and H. Okano, "Simulation-Based Approach to the Warehouse Location Problem for a Large Scale Real Instance", Proceedings of Winter Simulation Conference, 1997.
  • K. Hidaka and H. Okano, "Practical Approach to a Facility Location Problem for Large-Scale Logistics", Proceedings of ISAAC'97, 1997.
  • H. Okano, S. Misono, and K. Iwano, "New TSP Construction Heuristics and Their Relationships to the 2-Opt", 5th International Workshop on Algorithms and Data Structures, 1997.
  • H. Okano, S. Misono, and K. Iwano, "Extension of Traveling Salesman Heuristics for Vehicle Routing and Experiments with a Digital Road Map", 16th International Symposium on Mathematical Programming, 1997.
  • M. Amano, T. Yoshizumi, and H. Okano, "The Modal-Shift Transportation Planning Problem and Its Fast Steepest Descent Algorithm", Proceedings of the 2003 Winter Simulation Conference, 2003.
• Domestic conference
  • K. Hidaka and H. Okano, "An Approach to the Warehouse Location Problem using Digital Map", the 1997 Spring National Conference of ORSJ. (in Japanese)
  • H. Okano, S. Misono, and K. Iwano, "Experimental Analysis of TSP Heuristics and Proposal of a New Construction Heuristic That is Efficient When Postprocessed by the 2-Opt", IPSJ 55th Annual Meeting, 1997. (in Japanese)
  • H. Okano, "A New Escape Method in an Iterated-Local-Search-Based Algorithm for the Vehicle Routing Problem", the 1998 Fall National Conference of ORSJ. (in Japanese)
  • H. Okano, "Guiding Methods of Local Search for the Vehicle Routing Problem with Time Windows", the 1999 Fall National Conference of ORSJ. (in Japanese)

• GIS information
• Super-IFMAP