IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v49y2002i6p574-592.html
   My bibliography  Save this article

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Author

Listed:
  • S. Raghavan
  • Michael O. Ball
  • Vinai S. Trichur

Abstract

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031

Suggested Citation

  • S. Raghavan & Michael O. Ball & Vinai S. Trichur, 2002. "Bicriteria product design optimization: An efficient solution procedure using AND/OR trees," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(6), pages 574-592, September.
    • Handle: RePEc:wly:navres:v:49:y:2002:i:6:p:574-592
    DOI: 10.1002/nav.10031
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.10031
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.10031?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Namorado Climaco, Joao Carlos & Queiros Vieira Martins, Ernesto, 1982. "A bicriterion shortest path algorithm," European Journal of Operational Research, Elsevier, vol. 11(4), pages 399-404, December.
    2. Julie A. Ward, 1999. "Minimum-Aggregate-Concave-Cost Multicommodity Flows in Strong-Series-Parallel Networks," Mathematics of Operations Research, INFORMS, vol. 24(1), pages 106-129, February.
    3. Mote, John & Murthy, Ishwar & Olson, David L., 1991. "A parametric approach to solving bicriterion shortest path problems," European Journal of Operational Research, Elsevier, vol. 53(1), pages 81-92, July.
    4. V. Srinivasan & G. L. Thompson, 1972. "An operator theory of parametric programming for the transportation problem‐I," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 19(2), pages 205-225, June.
    5. V. Srinivasan & G. L. Thompson, 1972. "An operator theory of parametric programming for the transportation problem‐II," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 19(2), pages 227-252, June.
    6. Schaffers, M., 1990. "A polynomial algorithm for the single source network flow design problem on series-parallel graphs," LIDAM Discussion Papers CORE 1990062, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xie, Chi & Travis Waller, S., 2012. "Parametric search and problem decomposition for approximating Pareto-optimal paths," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1043-1067.
    2. Soroush, H.M., 2008. "Optimal paths in bi-attribute networks with fractional cost functions," European Journal of Operational Research, Elsevier, vol. 190(3), pages 633-658, November.
    3. Luigi Di Puglia Pugliese & Francesca Guerriero, 2013. "A Reference Point Approach for the Resource Constrained Shortest Path Problems," Transportation Science, INFORMS, vol. 47(2), pages 247-265, May.
    4. Zhang, Yuli & Shen, Zuo-Jun Max & Song, Shiji, 2016. "Parametric search for the bi-attribute concave shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 150-168.
    5. Granat, Janusz & Guerriero, Francesca, 2003. "The interactive analysis of the multicriteria shortest path problem by the reference point method," European Journal of Operational Research, Elsevier, vol. 151(1), pages 103-118, November.
    6. F. Guerriero & R. Musmanno, 2001. "Label Correcting Methods to Solve Multicriteria Shortest Path Problems," Journal of Optimization Theory and Applications, Springer, vol. 111(3), pages 589-613, December.
    7. Opasanon, Sathaporn & Miller-Hooks, Elise, 2006. "Multicriteria adaptive paths in stochastic, time-varying networks," European Journal of Operational Research, Elsevier, vol. 173(1), pages 72-91, August.
    8. Andrea Raith & Judith Wang & Matthias Ehrgott & Stuart Mitchell, 2014. "Solving multi-objective traffic assignment," Annals of Operations Research, Springer, vol. 222(1), pages 483-516, November.
    9. Xiang Zhang & David Rey & S. Travis Waller & Nathan Chen, 2019. "Range-Constrained Traffic Assignment with Multi-Modal Recharge for Electric Vehicles," Networks and Spatial Economics, Springer, vol. 19(2), pages 633-668, June.
    10. Perny, Patrice & Spanjaard, Olivier, 2005. "A preference-based approach to spanning trees and shortest paths problems***," European Journal of Operational Research, Elsevier, vol. 162(3), pages 584-601, May.
    11. Martins, Lucia & Craveirinha, Jose & Climaco, Joao N. & Gomes, Teresa, 2005. "On a bi-dimensional dynamic alternative routing method," European Journal of Operational Research, Elsevier, vol. 166(3), pages 828-842, November.
    12. Androutsopoulos, Konstantinos N. & Zografos, Konstantinos G., 2009. "Solving the multi-criteria time-dependent routing and scheduling problem in a multimodal fixed scheduled network," European Journal of Operational Research, Elsevier, vol. 192(1), pages 18-28, January.
    13. Matthias Müller-Hannemann & Karsten Weihe, 2006. "On the cardinality of the Pareto set in bicriteria shortest path problems," Annals of Operations Research, Springer, vol. 147(1), pages 269-286, October.
    14. Olaf Jahn & Rolf H. Möhring & Andreas S. Schulz & Nicolás E. Stier-Moses, 2005. "System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion," Operations Research, INFORMS, vol. 53(4), pages 600-616, August.
    15. Breugem, T. & Dollevoet, T.A.B. & van den Heuvel, W., 2016. "Analysis of FPTASes for the Multi-Objective Shortest Path Problem," Econometric Institute Research Papers EI2016-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    16. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    17. Dias, Luis C. & Climaco, Joao N., 2000. "Shortest path problems with partial information: Models and algorithms for detecting dominance," European Journal of Operational Research, Elsevier, vol. 121(1), pages 16-31, February.
    18. Ehrgott, Matthias & Tenfelde-Podehl, Dagmar, 2003. "Computation of ideal and Nadir values and implications for their use in MCDM methods," European Journal of Operational Research, Elsevier, vol. 151(1), pages 119-139, November.
    19. Sedeño-Noda, Antonio & Alonso-Rodríguez, Sergio, 2015. "An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem," Applied Mathematics and Computation, Elsevier, vol. 265(C), pages 602-618.
    20. Dunker, Thomas & Radons, Gunter & Westkamper, Engelbert, 2005. "Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem," European Journal of Operational Research, Elsevier, vol. 165(1), pages 55-69, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:49:y:2002:i:6:p:574-592. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.