A PC-based interactive decision support system for two objective direct delivery problems

Journal of Business Logistics, 1994 by Coutinho-Rodrigues, J M, Climaco, J C N, Current, John R

Routing problems are frequently multiobjective in nature. That is, the selection of a route from an origin to a destination is influenced by more than one objective. For example, the logistics planner may want to minimize the cost of the route, the total expected time to traverse the route, and/or the worst-case time to traverse the route. Unfortunately, the objectives in multiobjective routing problems are often in conflict. When this is true, no single route is optimal for all of the objectives. For example, the route that minimizes total cost may not be the route that minimizes delivery time. In such cases, the logistics manager must analyze the tradeoffs among the various objectives that exist among the various routes and select the option that best reflects his or her preferences. Ideally, the decision maker (DM) wants to consider only those options that are noninferior or efficient ones. An efficient solution is one in which the improvement in one of the objectives necessitates a degradation in one or more of the other objectives. The set of such solutions is referred to as the efficient frontier or noninferior solution set of the problem. For example, a hypothetical efficient frontier is shown in Figure 1. (Figure 1 omitted) Assume that the first objective, Z sub 1 , is to minimize route cost, and the second objective, Z sub 2 , is to minimize total travel time. Points A, B, C, D, and E represent the objective function values for 5 routes.

Routes A, B, C, and D are members of the efficient frontier for this particular problem. Solution A is the route that minimizes transportation cost and solution D is the one that minimizes total travel time. Routes B and C represent intermediate or compromise solutions. Route E represents an inferior solution and is not a member of the efficient frontier as route C is better than E in both objectives and should therefore be preferred over E. Given the efficient frontier, the decision maker may analyze the tradeoffs and select the route that best represents his or her preferences. For example, in moving from route A to route B, one obtains a relatively large reduction in travel time for a rather modest increase in total cost. However, when moving from route C to D, one must incur a relatively large increase in Z sub 1 (cost) for a relatively modest reduction in Z sub 2 (travel time). The actual route selected will depend on the magnitude of the objective function values and the logistics manager's preferences.

Such management science techniques as multiobjective programming may be used to generate the efficient frontier of multiobjective routing problems.(1) However, the efficient frontier may include a very large number of options(2) and individual routes may require considerable computation time to generate,(3) even for the most basic routing problem, the shortest path problem.(4) Consequently, it is generally impractical to generate the entire efficient frontier for most realistic logistics routing problems. In this paper, we demonstrate how interactive decision support systems may be used to help decision makers identify the best compromise solution to a two-objective routing problem.

The research presented in this paper is aimed specifically at developing a method to enable decision makers to identify the inherent trade offs in two-objective, shortest path problems. To be effective in decision support, the method must provide the DM with sufficient information to make an informed decision, yet be efficient enough for practical sized problems to be analyzed on a personal computer. In this paper we present a menu-drive, PC-based, interactive decision support system for generating an approximation of the efficient frontier of two-objective shortest path problems. The system provides the DM with information regarding the relevant tradeoffs involved in order to determine the best compromise solution. This progressive learning of the efficient options is directed to regions of the noninferior solution set that are selected by the DM as potentially containing solutions of interest. The system is based upon the procedure proposed in Current et al.(5) However, significant improvement in the method has enabled us to implement the procedure on a personal computer. The specifics of these improvements are given in Coutinho et al.(6) Henceforth, we refer to the system as PC-IDS (personal computer-based interactive decision support).

The remainder of this paper is organized as follows. In the next section, we describe the sample application that we use to demonstrate how PC-IDS works. The demonstration is presented in Section 3, and a summary is given in Section 4.

SAMPLE APPLICATION

Although PC-IDS is applicable to any two-objective path problem where both objectives are to be minimized, we demonstrate it on the following problem. Given the road network in Figure 2, the problem is to find the most preferred route from the source node, 1 (say a supplier of component parts), to the sink node, 5 say a final assembly plant). (Figure 2 omitted) The direct cost of the route chosen is an obvious selection criterion and results in the first objective, which is to minimize the transportation cost. As firms move to Just-in-Time manufacturing strategies, timeliness of delivery is also an important criterion in transportation route selection. Travel time on certain arcs may vary greatly due to congestion, accidents, maintenance, toll queues, and inspection station delays, among other factors. As a result, the second objective is to minimize the maximum travel time on the route. Table 1 lists the transportation cost, c(ij), for including arc (ij) on the route, and the maximum travel time, d(ij), required to traverse arc (ij). (Table 1 omitted) The c(ij) cost is based upon length and average travel time required to traverse arc (ij) and d(ij) is based upon the worst-case travel time to traverse arc (ij). This problem is formulated as a two-objective optimization problem in the Appendix.