daily pastebin goal
34%
SHARE
TWEET

Untitled

a guest Jan 17th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "BAPTVPartitioner.h"
  2.  
  3. using std::cout;
  4. using std::cerr;
  5. using std::endl;
  6. using std::ifstream;
  7. using std::ofstream;
  8. using std::ios;
  9. using std::setprecision;
  10.  
  11.  
  12.  
  13. BAPTVPartitioner::BAPTVPartitioner(BAPPackage& aPackage)
  14. :  BAPPartitioner(aPackage),           // init base class
  15.    mNumVes(aPackage.NumVessels()),
  16.    mVes(array<TVVessel>(1, mNumVes)),
  17.    mNumSect(aPackage.NumSections()),
  18.    mSect(array<TVSection>(1, mNumSect)),
  19.    mTrans(aPackage.Transhipments()),
  20.    mDist(aPackage.Distances()),
  21.    mTraceFile(mPackage.PartitioningTraceFilename()),
  22.    mRuntimeAnalyzer(0),
  23.    mSolnExists(false)
  24. {
  25.    gettimeofday(&mStartTime, NULL);
  26.    array<int>  temp;
  27.    
  28.    // Init vessel array with vessel objects
  29.    temp = aPackage.VesselLengths();
  30.    
  31.    for (int i = 1; i <= mNumVes; i++)
  32.    {
  33.       TVVessel v(i, temp[i]);
  34.       v.StartTimeZone(aPackage.StartTimeZone(i));
  35.       v.EndTimeZone(aPackage.EndTimeZone(i));
  36.       v.Arrival(aPackage.Arrival(i));
  37.       v.Departure(aPackage.Departure(i));
  38.      
  39.       // find all neighbouring vessels
  40.       for (int j = 1; j <= mNumVes; j++)
  41.       {
  42.          if (j == i) continue;         // ignore self loop
  43.          
  44.          if (mTrans(i, j) > 0  ||  mTrans(j, i) > 0)
  45.          {
  46.             v.AddNeighbour(j);
  47.             v.AddTranshipment(mTrans(i, j));
  48.             v.AddTranshipment(mTrans(j, i));
  49.          }
  50.       }
  51.  
  52.       v.Export(mTrans(0, i));
  53.       v.Import(mTrans(i, 0));
  54.       mVes[i] = v;
  55.    }
  56.  
  57.    // Init section array with section objects
  58.    temp = aPackage.SectionLengths();
  59.    
  60.    for (int i = 1, t = aPackage.NumTimeZones(); i <= mNumSect; i++)
  61.       mSect[i] = TVSection(i, t, temp[i]);
  62.  
  63.    ReadParameterFile();
  64. }
  65.  
  66.  
  67. BAPTVPartitioner::~BAPTVPartitioner()
  68. {
  69.    // nothing to do
  70. }
  71.  
  72.  
  73. void BAPTVPartitioner::Print(const int& aWidth,
  74.                              const int& aDetail) const
  75. {
  76.    cout  << "--== BAPTVPartitioner ==--" << endl
  77.          << "  ID = " << ID() << endl
  78.          << "  Name = " << Name() << endl
  79.          << "  Number of sections = " << mNumSect
  80.          << ", Number of vessels = " << mNumVes << endl
  81.          << "  Random seed = " << mRandomSeed << endl
  82.          << "  Transhipment = " << mTranshipment
  83.          << ", Penalty = " << mPenalty << endl << endl;
  84.  
  85.    for (int i = 1; i <= mNumVes; i++)
  86.       if (aDetail > 0)
  87.          mVes[i].Print(aWidth, aDetail);
  88.       else
  89.          cout  << "ves " << setw(4) << i
  90.                << " in sect " << setw(2) << mVes[i].Section() << endl;
  91.  
  92.    for (int k = 1; k <= mNumSect; k++)
  93.       if (aDetail > 0)
  94.          mSect[k].Print(aWidth, aDetail);
  95.       else
  96.       {
  97.          cout  << "sect " << setw(2) << k << " with vessels: " << endl;
  98.          int   i;
  99.          const set<int>& V = mSect[k].Vessels();
  100.          forall(i, V)
  101.          {
  102.             cout << i << " ";
  103.          }
  104.          cout << endl;
  105.       }
  106. }
  107.  
  108.  
  109. // The Solve method is called to perform
  110. // the vessel partitioning algorithm.
  111. //   this version calls GenerateInitialSolution
  112. //    (which creates a random initial solution)
  113. //
  114. void BAPTVPartitioner::Solve()
  115. {
  116.  
  117.    GenerateInitialSolution();
  118.    CalcInitialObjVal();
  119.  
  120.    gettimeofday(&mEndTime, NULL);
  121.  
  122.    PrintSummary();
  123.    WriteSolutionFile();
  124.    UpdatePackage();
  125. }
  126.  
  127.  
  128. void BAPTVPartitioner::PrintSummary() const
  129. {
  130.    cout  << mPackage.ProjectFilename() << " --- "
  131.          << mNumVes << " vessels, " << mNumSect << " sections" << endl
  132.          << "Transhipment = " << mTranshipment << endl
  133.          << "Penalty      = " << mPenalty << endl
  134.          << "Obj Value    = " << CalcObjVal() << endl
  135.          << "Time taken (sec) = "
  136.          << (mEndTime.tv_sec - mStartTime.tv_sec) +
  137.             (mEndTime.tv_usec - mStartTime.tv_usec) / 1000000.0
  138.          << endl
  139.          << endl;
  140. }
  141.  
  142.  
  143.  
  144. void BAPTVPartitioner::InitSolution()
  145. {
  146.    // Init working variables
  147.    mTranshipment = 0;
  148.    mPenalty = 0;
  149.    mUnallocVes.clear();
  150.    for (int i = 1; i <= mNumVes; i++)
  151.    {
  152.       mVes[i].Section(UNASSIGNED);   // all vessels unassigned
  153.       mUnallocVes.insert(i);
  154.    }
  155.  
  156.    ResetVesselDestinations();
  157. }
  158.  
  159. void BAPTVPartitioner::ResetVesselDestinations()
  160. {
  161.    // Add potential destination sections to each vessel
  162.    for (int i = 1; i <= mNumVes; i++)
  163.       for (int k = 1; k <= mNumSect; k++)
  164.          if (k != mVes[i].Section())
  165.             mVes[i].AddDestination(k);
  166. }
  167.  
  168.  
  169. void BAPTVPartitioner::CalcInitialObjVal()
  170. {
  171.    ComputeObjVal(mTranshipment, mPenalty);
  172. }
  173.  
  174.  
  175. void BAPTVPartitioner::ComputeObjVal(unsigned long& aTrans,
  176.                                      unsigned long& aPenalty) const
  177. {
  178.    aTrans = aPenalty = 0;
  179.  
  180.    for (int v1 = 1; v1 <= mNumVes; v1++)
  181.    {
  182.       const int&        s1 = mVes[v1].Section();
  183.       const set<int>&   neighbours = mVes[v1].Neighbours();
  184.       int               v2;
  185.  
  186.       // Calculate inter-vessel transhipment costs
  187.       forall(v2, neighbours)
  188.       {
  189.          if (v2 < v1) continue;
  190.  
  191.          const int&     s2 = mVes[v2].Section();
  192.          
  193.          if (s1 == UNASSIGNED  ||  s2 == UNASSIGNED)
  194.             aPenalty += TotalFlow(v1, v2) * LONGDISTANCE;
  195.          else
  196.          {
  197.             aTrans += TotalFlow(v1, v2) * D(s1, s2);
  198. //            cout  << setw(4) << v1 << setw(5) << v2
  199. //                  << setw(10) << TotalFlow(v1, v2) << " * "
  200. //                  << setw(5) << D(s1, s2) << " = "
  201. //                  << TotalFlow(v1, v2) * D(s1, s2)
  202. //                  << "     Trans = " << aTrans << endl;
  203.          }
  204.       }
  205.  
  206.       // Calculate import,export costs
  207.       if (s1 == UNASSIGNED)
  208.          aPenalty += (mVes[v1].Import() + mVes[v1].Export()) * LONGDISTANCE;
  209.       else
  210.       {
  211.          aTrans += (mVes[v1].Import() + mVes[v1].Export()) * D(s1, 0);
  212. //            cout  << setw(4) << v1 << " ("
  213. //                  << setw(5) << mVes[v1].Import() << " + "
  214. //                  << setw(5) << mVes[v1].Export() << ") * "
  215. //                  << setw(5) << D(s1, 0) << " = "
  216. //                  << (mVes[v1].Import() + mVes[v1].Export()) * D(s1, 0)
  217. //                  << "     Trans = " << aTrans << endl;
  218.       }
  219.    }
  220. }
  221.  
  222.  
  223. unsigned long BAPTVPartitioner::CalcObjVal() const
  224. {
  225.    unsigned long  ObjVal = mTranshipment + mPenalty;
  226.  
  227.    // Safeguards against overflow
  228.    assert(ObjVal >= mTranshipment);
  229.    assert(ObjVal >= mPenalty);
  230.  
  231.    return ObjVal;
  232. }
  233.  
  234. unsigned int BAPTVPartitioner::TotalFlow(const int& v1, const int& v2) const
  235. {
  236.    return (unsigned int) (mTrans(v1, v2) + mTrans(v2, v1));
  237. }
  238.  
  239. unsigned int BAPTVPartitioner::TotalFlow(const TVVessel& v1, const TVVessel& v2) const
  240. {
  241.    return (unsigned int) (mTrans(v1.ID(), v2.ID()) + mTrans(v2.ID(), v1.ID()));
  242. }
  243.  
  244. unsigned int BAPTVPartitioner::D(const int& s1, const int& s2) const
  245. {
  246.    if (s1 >= 0  &&  s2 >= 0)           // take port into account also
  247.       return (unsigned int) mDist(s1, s2);
  248.    else
  249.       return LONGDISTANCE;
  250. }
  251.  
  252. unsigned int BAPTVPartitioner::D(const TVSection& s1, const TVSection& s2) const
  253. {
  254.    if (s1.ID() >= 0  &&  s2.ID() >= 0) // take port into account also
  255.       return (unsigned int) mDist(s1.ID(), s2.ID());
  256.    else
  257.       return LONGDISTANCE;
  258. }
  259.  
  260.  
  261. void BAPTVPartitioner::UpdatePackage() const
  262. {
  263.    for (int i = 1; i <= mNumVes; i++)
  264.       mPackage.SectionAssignedTo(i, mVes[i].Section());
  265.    
  266.    mPackage.TranshipmentCost(mTranshipment);
  267.  
  268.    // What happened to the penalty?!?
  269. }
  270.  
  271.  
  272. void BAPTVPartitioner::ReadParameterFile()
  273. {
  274.    string   paramFile = mPackage.ParamFilename();
  275.    char     buf[255];
  276.    string   token, mode = "nil";
  277.    ifstream ParamFile(paramFile);
  278.  
  279.    if (!ParamFile)
  280.    {
  281.       cerr << "Cannot open parameter file: " << paramFile << endl;
  282.       return;
  283.    }
  284.  
  285.    while (!ParamFile.eof())
  286.    {
  287.       ParamFile.getline(buf,80);
  288.  
  289. #ifdef _DEBUG
  290.          cout << "tokenizing: " << buf << endl;
  291. #endif
  292.  
  293.       for (int i = 0; i < 80; i++)     // Convert carriage-return to space
  294.          if (13 == (int) buf[i])
  295.             buf[i] = ' ';
  296.  
  297.       if (buf[0] == ' ' || buf[0] == 0)
  298.          continue;
  299.  
  300.       token = strtok(buf, " ");
  301.  
  302. #ifdef _DEBUG
  303.       cout << "token = " << token << endl;
  304. #endif
  305.  
  306.       if (token.length() == 0)         // empty line, ignore
  307.          continue;
  308.       if (token == "#")                // comment line, ignore
  309.          continue;
  310.       if (token[0] == '_')             // keyword, change mode
  311.          mode = token;
  312.       else                             // process data based on mode
  313.       {
  314.          if (mode == "_RANDOM_SEED")
  315.          {
  316.             mRandomSeed = atoi(token);
  317.             mRandom.set_seed(mRandomSeed);
  318.          }  
  319.          else if (mode == "_PRINT_SECTIONS")
  320.          {
  321.             mPrintSections = atoi(token);
  322.          }
  323.          else if (mode == "_PRINT_VESSELS")
  324.          {
  325.             mPrintVessels = atoi(token);
  326.          }
  327.          else if (mode == "_RUNTIME_ANALYZER")
  328.          {
  329.             mRuntimeAnalyzer = atoi(token);
  330.          }
  331.          else if (mode == "_SUMMARY")
  332.          {
  333.             mSummary = atoi(token);
  334.          }
  335.          // else nothing
  336.       }  
  337.    }
  338. }
  339.  
  340.  
  341. void BAPTVPartitioner::WriteSolutionFile() const
  342. {
  343.    string   solutionFile = mPackage.PartitioningFilename(),
  344.             paramFile = mPackage.ParamFilename();
  345.  
  346.    ofstream SolFile(solutionFile);
  347.  
  348.    if (!SolFile)
  349.    {
  350.       cerr << "Cannot create solution file: " << solutionFile << endl;
  351.       return;
  352.    }
  353.  
  354.    // Write comments
  355.    // ( Date() auto-inserts a carriage-return! )
  356.    SolFile  << "#" << endl
  357.             << "# Solution File created by BAPTVPartitioner" << endl
  358.             << "# Date = " << Date()
  359.             << "# Parameter File = " << paramFile << endl
  360.             << "#" << endl << endl;
  361.  
  362.    SolFile  << "_NUM_UNALLOCATED" << endl
  363.             << mUnallocVes.size() << endl << endl;
  364.  
  365.    // Reads from the BAP package
  366.    const int V = mNumVes;
  367.  
  368.    // Write solution information
  369.    SolFile.setf(ios::fixed);
  370.    SolFile  << "_NUM_VESSELS" << endl
  371.             << V + 1 << endl           // n+1 to account for port
  372.             << endl
  373.             << "_OBJECTIVE_VALUE" << endl
  374.             << setprecision(2) << mTranshipment + mPenalty << endl
  375.             << endl
  376.             << "_TRANSHIPMENT_VALUE" << endl
  377.             << setprecision(2) << mTranshipment << endl
  378.             << endl
  379.             << "_PENALTY_VALUE" << endl
  380.             << setprecision(2) << mPenalty << endl
  381.             << endl
  382.             << "_TIME_TAKEN" << endl
  383.             << setprecision(6)
  384.             << (mEndTime.tv_sec - mStartTime.tv_sec) +
  385.                (mEndTime.tv_usec - mStartTime.tv_usec) / 1000000.0
  386.             << endl
  387.             << endl;
  388.    SolFile.setf(ios::fixed, ios::floatfield);
  389.  
  390.    // Write allocated vessels
  391.    array<int>  Arrivals = mPackage.Arrivals(),
  392.                Departures = mPackage.Departures();
  393.  
  394.    SolFile  << "# Final Allocation Solution" << endl
  395.             << "# <ves#> <sect> <wharf> <berth time> <departure time>"
  396.             << endl << endl
  397.             << "_ALLOCATION" << endl;
  398.  
  399.    SolFile  << "0 0 0 0 0" << endl;    // Write the sea port
  400.  
  401.    for (int i = 1; i <= V; i++)
  402.       if (mVes[i].Section() > 0)
  403.          SolFile  << i << " " << mVes[i].Section() << " " << -1
  404.                   << " " << Arrivals[i] << " " << Departures[i]
  405.                   << endl;
  406.  
  407.    // Write unallocated vessels, if any
  408.    if (mUnallocVes.size() > 0)
  409.    {
  410.       SolFile  << endl << "_UNALLOCATED_VESSELS" << endl;
  411.  
  412.       for (int i = 1; i <= V; i++)
  413.          if (mVes[i].Section() < 0)
  414.             SolFile  << i << " " << -1 << " " << -1
  415.                      << " " << Arrivals[i] << " " << Departures[i]
  416.                      << endl;
  417.    }
  418.  
  419.    SolFile << endl << endl;
  420.  
  421.    SolFile.close();
  422. }
  423.  
  424.  
  425. void BAPTVPartitioner::WriteTraceFile(string aStr) const
  426. {
  427.    ofstream TraceFile(mTraceFile, ios::app);
  428.    TraceFile  << aStr << endl;
  429.    TraceFile.close();
  430. }
  431.  
  432. void BAPTVPartitioner::WriteTraceFile(long aLong) const
  433. {
  434.    ofstream TraceFile(mTraceFile, ios::app);
  435.    TraceFile   << aLong << endl;
  436.    TraceFile.close();
  437. }
  438.  
  439. void BAPTVPartitioner::WriteTraceFile(long double aDouble) const
  440. {
  441.    ofstream TraceFile(mTraceFile, ios::app);
  442.    TraceFile.setf(ios::fixed);
  443.    TraceFile  << setprecision(2) << aDouble << endl;
  444.    TraceFile.close();
  445. }
  446.  
  447.  
  448. string BAPTVPartitioner::Date() const
  449. {
  450.    //
  451.    // Query date and time
  452.    //
  453.    struct tm   *TimePtr;
  454.    time_t      Time;
  455.  
  456.    time(&Time);
  457.    TimePtr = localtime(&Time);
  458.  
  459.    return string(asctime(TimePtr));
  460. }
  461.  
  462. // GenerateInitialSolution creates a vessel partitioning solution.
  463. // At the moment, it creates a random initial solution.
  464. //   Called by: Solve();
  465. //
  466. void BAPTVPartitioner::GenerateInitialSolution()
  467. {
  468.    InitSolution();
  469.    GenSolnRandom();
  470. }
  471.  
  472.  
  473. // This method actually create the random vessel partitioning
  474. // solution. Each vessel is assigned a random section
  475. // At the moment, it creates a random initial solution.
  476. //   Called by: Solve();
  477. void BAPTVPartitioner::GenSolnRandom()
  478. {
  479.    // List of candidate vessels for allocation
  480.    array<int>  V(1, mNumVes);
  481.    
  482.    array<int>  temp;
  483.    
  484.    // Init vessel array with vessel objects
  485.    temp = aPackage.VesselLengths();
  486.    
  487.    for (int i = 1; i <= mNumVes; i++)
  488.       V[i] = i;                        // set content to vessel ID
  489.  
  490.    // Loop to do actual allocation
  491.    int   i, VesselsLeft = mNumVes;
  492.  
  493.    while (VesselsLeft > 0)
  494.    {
  495.    int VmaxLength=0;
  496.      for ( int k=1; i<=VesselsLeft; i++)
  497.      {
  498.         TVVessel v(k, temp[k]);
  499.         int len= v.Length(aPackage.Length(k));
  500.       if ( len > VmaxLength)
  501.       {
  502.        VmaxLength= len;
  503.        i=k;
  504.       }
  505.      }
  506.       // randomly pick a vessel
  507.       int         vIndex = V[i];
  508.       TVVessel&   v = mVes[vIndex];
  509.       AssignVesselToRandomSection(v);
  510.       // remove assigned vessel by replacing it with last vessel
  511.       V[i] = V[VesselsLeft];
  512.       VesselsLeft--;
  513.    }
  514. }
  515.  
  516.  
  517. // Assigns Vessel v to a random section
  518. //   Alg: save the candidate destination sections
  519. //        for each randomly selected section
  520. //        assign to it if there is room for it
  521. //        else remove the section.
  522. //   Note:vessel is unassigned if all sections fails.
  523. //
  524. void BAPTVPartitioner::AssignVesselToRandomSection(TVVessel& v)
  525. {
  526.    // List of candidate sections to be assigned to v
  527.    set<int> sectSet = v.Destinations();   // Copy, preserve original
  528.    array<int> S(1, sectSet.size());       // Array of destination sections
  529.    int   i = 1, k;
  530.    
  531.    while (!sectSet.empty())
  532.    {
  533.       k = sectSet.choose();
  534.       sectSet.del(k);
  535.       S[i++] = k;
  536.    }
  537.  
  538.    // Loop to do actual assignment
  539.    int   SectionsLeft = S.size();
  540.  
  541.    while (SectionsLeft > 0  &&  v.Section() == UNASSIGNED)
  542.    {
  543.       i = mRandom(1, SectionsLeft);  // randomly pick a section
  544.       int      k = S[i];
  545.      
  546.       if (mSect[k].CanAccommodate(v))
  547.          Assign(v, mSect[k]);
  548.       else
  549.          S[i--] = S[SectionsLeft--]; // remove from further consideration
  550.    }
  551. }
  552.  
  553.  
  554. void BAPTVPartitioner::Assign(TVVessel& v, TVSection& s)
  555. {
  556.    v.Section(s.ID());
  557.    v.RemoveDestination(s.ID());
  558.    s.Add(v);
  559.    mUnallocVes.del(v.ID());
  560. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top