عکس salehafzoon
Solving SOP with SA, GRASP, Tabu Search algorithms. Include an analytic report.Python
موضوع‌ها
۰
فورک‌ها
۰
ستاره‌ها
۱۱
تاریخ ایجاد
۲۳ مرداد ۱۳۹۹
آخرین بروزرسانی
بیشتر از ۱ سال قبل

SOP optimization

Solving SOP with SA, GRASP, Tabu Search algorithms.

python implemented Python 3.9.4

Problem Description

The Sequential Ordering Problem (SOP) with precedence constraints consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the arcs and on the nodes, subject to precedence constraints among nodes.

Instance Description

TSPLIB is a library of sample instanes for the TSP (and related problems) from various soures and of various types. Instanes of the following problem classes are available:

  • Symmetric traveling salesman problem (TSP)
  • Hamiltonian cycle problem (HCP)
  • Asymmetric traveling salesman problem (ATSP)
  • Sequential ordering problem (SOP)
  • Capaitated vehicle routing problem (CVRP)
  • The file format

    Each file consists of specification part and of a data part. The specification part contains information on the file format and on its contents. The data part contains explicit data. python implementation

Algorithms

All the algorithms are designed base on the Lexicographic Search using forwarding and back warding path-preserving-3-exchange as explained in An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem paper.

Running

Just go to related algorithm directory and run the python code. example:

 cd ./SA
 python main.py

Results

All results and comparing analyze are presented in Report.pdf files. overal algorithms comparisons result is as follow:

  • SA

    Instance BKS best average worst avg_time
    ESC78.sop 18230 18250 18400.5 18400.5 1.7924
    susan.260.158.sop 1016 1123 1128.8 1136 8.6370
    R.200.100.1.sop 61 340 402.3 453 28.773
  • GRASP

    Instance BKS best average worst avg_time
    ESC78.sop 18230 20405 20895 21220 3.8190
    susan.260.158.sop 1016 1123 1128.8 1136 8.6370
    R.200.100.1.sop 61 393 448.7 483 56.704
  • Instance BKS best average worst avg_time
    ESC78.sop 18230 18515 18967.5 19325 1.8291
    susan.260.158.sop 1016 1043 1061.7 1078 1.3065
    R.200.100.1.sop 61 489 595.5 651 27.902

References