A physarum polycephalum optimization algorithm for the bi-objective shortest path problem

Xiaoge Zhang, Qing Wang, Tung Sun Chan, Sankaran Mahadevan, Yong Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)


Multi-objective shortest path problem (MOSP) plays an important role in practical applications, which seeks for the efficient paths satisfying several conflicting objectives between two nodes of a network. In this paper, we present an algorithm based on Physarum Polycephalum model to solve the bi-objective shortest path problem. By aggregating the two attributes into one by weighted sum, we successfully convert the bi-objective shortest path problem (BOSP) into the shortest path problem. Here, in order to reduce the computational time, binary weight allocation (BWA) technique is implemented to distribute the weight for each criterion. To check the quality of the proposed method and the accuracy of the algorithm, experimental analyzes are conducted. Random networks are generated to verify the accuracy of the proposed algorithm. Results on the testing problems are compared with label correcting algorithm known as an efficient algorithm for solving the BOSP. The results demonstrate the proposed Physarum Polycephalum optimization algorithm can produce the non-dominated solutions successfully when dealing with the BOSP.
Original languageEnglish
Pages (from-to)143-162
Number of pages20
JournalInternational Journal of Unconventional Computing
Issue number1-2
Publication statusPublished - 25 Nov 2013


  • Biobjective shortest path problem
  • Pareto frontiers
  • Physarum polycephalum
  • Shortest path problem

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'A physarum polycephalum optimization algorithm for the bi-objective shortest path problem'. Together they form a unique fingerprint.

Cite this