[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Uncertain multi-objective Chinese postman problem

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Chinese postman problem is one of the significant combinatorial optimization problems with a wide range of real-world applications. Modelling such real-world applications quite often needs to consider some uncertain factors for which the belief degrees of the experts are essential. Liu (Uncertainty Theory, 2nd edn. Springer, Berlin, 2007) proposed uncertainty theory to model such human beliefs. This paper presents a multi-objective Chinese postman problem under the framework of uncertainty theory. The objectives of the problem are to maximize the total profit earned and to minimize the total travel time of the tour of a postman. Here, we have proposed an expected value model (EVM) for the uncertain multi-objective Chinese postman problem (UMCPP). The deterministic transformation of the corresponding EVM is done by computing the expected value of the uncertain variable using 999-method for which we have proposed an algorithm, 999-expected value model-uncertain multi-objective Chinese postman problem. Subsequently, the model is solved by two classical multi-objective solution techniques, namely global criterion method and fuzzy programming method. Two multi-objective genetic algorithms (MOGAs): nondominated sorting genetic algorithm II and multi-objective cross-generational elitist selection, heterogeneous recombination and cataclysmic mutation are also used to solve the model. A numerical example is presented to illustrate the proposed model. Finally, the performance of MOGAs is compared on six randomly generated instances of UMCPP.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Chen X, Gao J (2013) Uncertain term structure model of interest rate. Soft Comput 17(4):597–604

    Article  MATH  Google Scholar 

  • Chen L, Peng J, Zhang B, Rosyida I (2016) Diversified models for portfolio selection based on uncertain semivariance. Int J Syst Sci 48(3):637–648

    Article  MathSciNet  MATH  Google Scholar 

  • Chen B, Liu Y, Zhou T (2017) An entropy based solid transportation problem in uncertain environment. J Ambient Intell Humanized Comput. https://doi.org/10.1007/s12652-017-0535-z

    Article  Google Scholar 

  • Chen Y, Gao J, Yang G, Liu Y (2018) Solving equilibrium standby redundancy optimization problem by hybrid PSO algorithm. Soft Comput 22(17):5631–5645

    Article  MATH  Google Scholar 

  • Christofides N, Campos V, Corberan A, Mota E (1981) An algorithm for the rural postman problem. Imperial College report IC-OR

  • Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

    Google Scholar 

  • Ding S (2014) Uncertain minimum cost flow problem. Soft Comput 18:2201–2207

    Article  MATH  Google Scholar 

  • Ding S (2015) The α-maximum flow model with uncertain capacities. Appl Math Model 39:2056–2063

    Article  MathSciNet  Google Scholar 

  • Durillo JJ, Nebro AJ (2011) jMetal: a Java framework for multi-objective optimization. Adv Eng Softw 42(10):760–771

    Article  Google Scholar 

  • Erdős P, Rényi A (1959) On random graphs. Publ Math 6:290–297

    MathSciNet  MATH  Google Scholar 

  • Eshelman LJ (1991) The CHC adaptive search algorithm: how to have safe search when engaging. Found Genet Algorithm 1:265–283

    Google Scholar 

  • Fonseca CM, Fleming PJ (1993) Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In: Proceedings of the fifth international conference on genetic algorithms, San Francisco, CA, USA, pp 416–423

  • Gao Y (2011) Shortest path problem with uncertain arc lengths. Comput Math Appl 62:2591–2600

    Article  MathSciNet  MATH  Google Scholar 

  • Gao R, Sun Y, Ralescu D (2016) Order statistics of uncertain random variables with application to k-out-of-n system. Fuzzy Optim Decis Mak 16(2):159–181

    Article  MathSciNet  MATH  Google Scholar 

  • Gilbert E (1959) Random graphs. Ann Math Stat 30(4):1141–1144

    Article  MATH  Google Scholar 

  • Golden B, Wong R (1981) Capacitated arc routing problems. Networks 11(3):305–315

    Article  MathSciNet  MATH  Google Scholar 

  • Grandinetti L, Guerriero F, Laganà D, Pisacane O (2010) An approximate ε-constraint method for the multi-objective undirected capacitated arc routing problem. In: SEA’10 proceedings of the 9th international conference on experimental algorithms, Naples, Italy, pp 214–225

    Chapter  Google Scholar 

  • Guan M (1984) On the windy postman problem. Discrete Appl Math 9(1):41–46

    Article  MathSciNet  MATH  Google Scholar 

  • Guo C, Gao J (2017) Optimal dealer pricing under transaction uncertainty. J Intell Manuf 28(3):657–665

    Article  Google Scholar 

  • Han S, Peng Z, Wang S (2014) The maximum flow problem of uncertain network. Inf Sci 265:167–175

    Article  MathSciNet  MATH  Google Scholar 

  • Hu Z, Gao J (2018) Uncertain Gompertz regression model with imprecise observations. Soft Comput. https://doi.org/10.1007/s00500-018-3611-1

    Article  Google Scholar 

  • Kar MB, Majumder S, Kar S, Pal T (2017) Cross-entropy based multi-objective uncertain portfolio selection problem. J Intell Fuzzy Syst 32(6):4467–4483

    Article  MATH  Google Scholar 

  • Kwan MK (1962) Graphic programming using odd or even points. Chin Math 1:273–277

    MathSciNet  MATH  Google Scholar 

  • Lacomme P, Prins C, Sevaux M (2006) A genetic algorithm for a bi-objective capacitated arc routing problem. Comput Oper Res 33(12):3473–3493

    Article  MATH  Google Scholar 

  • Lin YX, Zhao YC (1988) A new algorithm for the directed Chinese postman problem. Comput Oper Res 15(6):577–584

    Article  MathSciNet  MATH  Google Scholar 

  • Liu B (2007) Uncertainty theory, 2nd edn. Springer, Berlin

    MATH  Google Scholar 

  • Liu B (2009a) Some research problems in uncertainty theory. J Uncertain Syst 3(1):3–10

    Google Scholar 

  • Liu B (2009b) Theory and practice of uncertain programming, 2nd edn. Springer, Berlin

    Book  MATH  Google Scholar 

  • Liu B (2010) Uncertainty theory: a branch of mathematics for modeling human uncertainty. Springer, Berlin

    Book  Google Scholar 

  • Liu B (2012) Why is there a need for uncertainty theory? J Uncertain Syst 6(1):3–10

    Google Scholar 

  • Liu YH, Ha MH (2010) Expected value of function of uncertain variables. J Uncertain Syst 4(3):181–186

    Google Scholar 

  • Liu L, Zhang B, Ma W (2017) Uncertain programming models for fixed charge multi-item solid transportation problem. Soft Comput. https://doi.org/10.1007/s00500-017-2718-0

    Article  MATH  Google Scholar 

  • Majumder S, Kundu P, Kar S, Pal T (2018a) Uncertain multi-objective multi-item fixed charge solid transportation problem with budget constraint. Soft Comput. https://doi.org/10.1007/s00500-017-2987-7

    Article  MATH  Google Scholar 

  • Majumder S, Kar S, Pal T (2018b) Mean-entropy model of uncertain portfolio selection problem. In: Mandal JK, Mukhopadhyay S, Dutta P (eds) Multi-objective optimization: evolutionary to hybrid framework. Springer, Singapore. https://doi.org/10.1007/978-981-13-1471-1_2

    Chapter  Google Scholar 

  • Nag K, Pal T, Pal NR (2015) ASMiGA: an archive-based steady-state micro genetic algorithm. IEEE Trans Cybern 45(1):40–52

    Article  Google Scholar 

  • Nebro AJ, Alba E, Molina G, Chicano F, Luna F, Durillo JJ (2007) Optimal antenna placement using a new multi-objective CHC algorithm. In: GECCO ‘07 proceedings of the 9th annual conference on genetic and evolutionary computation, New York, NY, USA, pp 876–883

  • Nobert Y, Picard JC (1996) An optimal algorithm for the mixed Chinese postman problem. Networks 27(2):95–108

    Article  MathSciNet  MATH  Google Scholar 

  • Nossack J, Golden B, Pesch E, Zhang R (2017) The windy rural postman problem with a time-dependent zigzag option. Eur J Oper Res 258(3):1131–1142

    Article  MathSciNet  MATH  Google Scholar 

  • Pearn WL (1994) Solvable cases of the k-person Chinese postman problem. Oper Res Lett 16(4):241–244

    Article  MathSciNet  MATH  Google Scholar 

  • Pearn WL, Chou JB (1999) Improved solutions for the Chinese postman problem on mixed networks. Comput Oper Res 26(8):819–827

    Article  MathSciNet  MATH  Google Scholar 

  • Pearn WL, Wang KH (2003) On the maximum benefit Chinese postman problem. Omega 31(4):269–273

    Article  Google Scholar 

  • Qin Z, Kar S (2013) Single-period inventory problem under uncertain environment. Appl Math Comput 219:9630–9638

    MathSciNet  MATH  Google Scholar 

  • Rao SS (2006) Engineering optimization-theory and practice, 3rd edn. New Age International Publishers, New Delhi

    Google Scholar 

  • Sheng Y, Yao K (2012) A transportation model with uncertain costs and demands. Information 15(8):3179–3186

    MathSciNet  MATH  Google Scholar 

  • Tan G, Cui X, Zhang Y (2005) Chinese postman problem in stochastic networks. In: ICAS/ICNS 2005 proceedings of the joint international conference on autonomic and autonomous systems and international conference on networking and services. IEEE Computer Society, Papeete, Tahiti, pp 78–78

  • Van Veldhuizen DA, Lamont GB (1998) Multi-objective evolutionary algorithm research: a history and analysis. Technical report TR-98-03, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson, AFB, OH

  • Wang H-F, Wen Y-P (2002) Time-constrained Chinese postman problems. Comput Math Appl 44(3–4):375–387

    Article  MathSciNet  MATH  Google Scholar 

  • Yan L (2009) Optimal portfolio selection models with uncertain returns. Mod Appl Sci 3(8):76–81

    Article  MATH  Google Scholar 

  • Yang X, Gao J (2013) Uncertain differential games with application to capitalism. J Uncertain Anal Appl. https://doi.org/10.1186/2195-5468-1-17

    Article  Google Scholar 

  • Yang X, Gao J (2016) Linear-quadratic uncertain differential game with application to resource extraction problem. IEEE Trans Fuzzy Syst 24(4):819–826

    Article  Google Scholar 

  • Yang X, Gao J (2017) Bayesian equilibria for uncertain bimatrix game with asymmetric information. J Intell Manuf 28(3):515–525

    Article  Google Scholar 

  • Zhang X, Chen X (2012) A new uncertain programming model for project scheduling problem. Information 15(10):3901–3910

    MathSciNet  MATH  Google Scholar 

  • Zhang B, Peng J (2012) Uncertain programming model for Chinese postman problem with uncertain weights. Ind Eng Manag Syst 11(1):18–25

    Google Scholar 

  • Zhang B, Peng J (2013) Uncertain programming model for uncertain optimal assignment problem. Appl Math Model 37(9):6458–6468

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang B, Peng J, Li S, Chen L (2016) Fixed charge solid transportation problem in uncertain environment and its algorithm. Comput Ind Eng 102(2016):186–197

    Article  Google Scholar 

  • Zhang Y, Gao J, An Q (2018) International investing in uncertain financial market. Soft Comput 22(16):5335–5346

    Article  MATH  Google Scholar 

  • Zhou A, Jin Y, Zhang Q, Sendho B, Tsang E (2006) Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. In: IEEE congress on evolutionary computation, Sheraton Vancouver Wall Center Vancouver, BC, Canada, pp 3234–3241

  • Zhou J, He X, Wang K (2014) Uncertain quadratic minimum spanning tree problem. J Commun 9(5):385–390

    Article  Google Scholar 

  • Zhou J, Chen L, Wang K (2015) Path optimality conditions for minimum spanning tree problem with uncertain edge weights. Int J Uncertain Fuzziness Knowl Based Syst 23(1):49–71

    Article  MathSciNet  MATH  Google Scholar 

  • Zimmermann H-J (1978) Fuzzy programming and linear programming with several objective functions. Fuzzy Sets Syst 1(1):45–55

    Article  MathSciNet  MATH  Google Scholar 

  • Zitzler E, Thiele L (1999) Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271

    Article  Google Scholar 

Download references

Acknowledgements

The authors are very much thankful to the Editor and the anonymous referees for their constructive and valuable suggestions to enhance the quality of the manuscript. Moreover, Saibal Majumder, an INSPIRE fellow (No.: DST/INSPIRE Fellowship/2015/IF150410) is indebted to the Department of Science & Technology (DST), Ministry of Science and Technology, Government of India, for providing him financial assistance for the work.

Author information

Authors and Affiliations

  1. Department of Computer Science, National Institute of Technology Durgapur, Durgapur, India

    Saibal Majumder & Tandra Pal

  2. Department of Mathematics, National Institute of Technology Durgapur, Durgapur, India

    Samarjit Kar

Authors
  1. Saibal Majumder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Samarjit Kar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tandra Pal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Samarjit Kar.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interest regarding the publication of this article.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Informed consent

Informed consent is obtained from all individual participants included in the study.

Additional information

Communicated by V. Loia.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A

Appendix A

In this section, we present some corollaries related to Theorem 4.1 (cf. Sect. 4).

Corollary A1

If\( \xi_{{a_{ij} }} \), \( \xi_{{c_{ij} }} \)and\( \xi_{{t_{ij} }} \)are the independent linear uncertain variables, which are, respectively, represented as\( {\mathcal{L}}\left( {p_{{a_{ij} }} ,q_{{a_{ij} }} } \right) \), \( {\mathcal{L}}\left( {p_{{c_{ij} }} ,q_{{c_{ij} }} } \right) \)and\( {\mathcal{L}}\left( {p_{{t_{ij} }} ,q_{{t_{ij} }} } \right). \)Then, model (16) presented in Theorem4.1can be written as model (A1).

$$ \left\{ {\begin{array}{*{20}l} {{\text{Max}}\; Z_{1} = \mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{j = 1,j \ne i}^{n} \left\{ {\left( {\frac{{p_{{a_{ij} }} + q_{{a_{ij} }} }}{2} - \frac{{p_{{c_{ij} }} + q_{{c_{ij} }} }}{2}} \right)\left( {x_{ij} + x_{ji} } \right)} \right\}} \hfill \\ {{\text{Min }}\;Z_{2} = \mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{j = 1,j \ne i}^{n} \left( {\frac{{p_{{t_{ij} }} + q_{{t_{ij} }} }}{2}} \right)\left( {x_{ij} + x_{ji} } \right)} \hfill \\ {{\text{subject}}\; {\text{to}}} \hfill \\ {\mathop \sum \limits_{j = 1}^{n} x_{ij} - \mathop \sum \limits_{k = 1}^{n} x_{ki} = 0, \quad i = 1,2, \ldots ,n} \hfill \\ {x_{ij} + x_{ji} \ge 1 ,\quad e_{ij} \in E_{G} } \hfill \\ {x_{ij} \in \left\{ {0,1} \right\} , \quad e_{ij} \in E_{G} }. \hfill \\ {} \hfill \\ \end{array} } \right. $$
(A1)

Corollary A2

If\( \xi_{{a_{ij} }} \), \( \xi_{{c_{ij} }} \)and\( \xi_{{t_{ij} }} \)are the independent zigzag uncertain variables, which are expressed as\( {\mathcal{Z}}\left( {p_{{a_{ij} }} ,q_{{a_{ij} }} ,r_{{a_{ij} }} } \right) \), \( {\mathcal{Z}}\left( {p_{{c_{ij} }} ,q_{{c_{ij} }} ,r_{{c_{ij} }} } \right) \) and \( {\mathcal{Z}}\left( {p_{{t_{ij} }} ,q_{{t_{ij} }} ,r_{{t_{ij} }} } \right) \), respectively. Then, model (16) reported in Theorem4.1can be represented as model (A2).

$$ \left\{ {\begin{array}{*{20}l} {{\text{Max}}\; Z_{1} = \mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{j = 1,j \ne i}^{n} \left\{ {\left( {\frac{{p_{{a_{ij} }} + 2q_{{a_{ij} }} + r_{{a_{ij} }} }}{4} - \frac{{p_{{c_{ij} }} + 2q_{{c_{ij} }} + r_{{c_{ij} }} }}{4}} \right)\left( {x_{ij} + x_{ji} } \right)} \right\}} \hfill \\ {{\text{Min }}\;Z_{2} = \mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{j = 1,j \ne i}^{n} \left( {\frac{{p_{{t_{ij} }} + 2q_{{t_{ij} }} + r_{{t_{ij} }} }}{2}} \right)\left( {x_{ij} + x_{ji} } \right)} \hfill \\ {{\text{subject}}\;{\text{to}}} \hfill \\ {\mathop \sum \limits_{j = 1}^{n} x_{ij} - \mathop \sum \limits_{k = 1}^{n} x_{ki} = 0, \quad i = 1,2, \ldots ,n} \hfill \\ {x_{ij} + x_{ji} \ge 1 ,\quad e_{ij} \in E_{G} } \hfill \\ {x_{ij} \in \left\{ {0,1} \right\} , \quad e_{ij} \in E_{G} }. \hfill \\ {} \hfill \\ \end{array} } \right. $$
(A2)

Corollary A3

If\( \xi_{{a_{ij} }} \), \( \xi_{{c_{ij} }} \)and\( \xi_{{t_{ij} }} \)are the independent normal uncertain variables, which are of the form\( {\mathcal{N}}\left( {m_{{a_{ij} }} ,\sigma_{{a_{ij} }} } \right) \), \( { \mathcal{N}}\left( {m_{{c_{ij} }} ,\sigma_{{c_{ij} }} } \right) \)and\( {\mathcal{N}}\left( {m_{{t_{ij} }} ,\sigma_{{t_{ij} }} } \right) \), respectively. Then, model (16) shown in Theorem4.1can be written as follows:

$$ \left\{ {\begin{array}{*{20}l} {{\text{Max}}\; Z_{1} = \mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{j = 1,j \ne i}^{n} \left\{ {\left( {m_{{a_{ij} }} - m_{{c_{ij} }} } \right)\left( {x_{ij} + x_{ji} } \right)} \right\}} \hfill \\ {{\text{Min }}\;Z_{2} = \mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{j = 1,j \ne i}^{n} m_{{t_{ij} }} \left( {x_{ij} + x_{ji} } \right)} \hfill \\ {{\text{subject}}\;{\text{to}}} \hfill \\ {\mathop \sum \limits_{j = 1}^{n} x_{ij} - \mathop \sum \limits_{k = 1}^{n} x_{ki} = 0, \quad i = 1,2, \ldots ,n} \hfill \\ {x_{ij} + x_{ji} \ge 1 ,\quad e_{ij} \in E_{G} } \hfill \\ {x_{ij} \in \left\{ {0,1} \right\} , \quad e_{ij} \in E_{G} }. \hfill \\ {} \hfill \\ \end{array} } \right. $$
(A3)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Majumder, S., Kar, S. & Pal, T. Uncertain multi-objective Chinese postman problem. Soft Comput 23, 11557–11572 (2019). https://doi.org/10.1007/s00500-018-03697-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-018-03697-3

Keywords

Search

Navigation