Title page for etd-0629117-234517


[Back to Results | New Search]

URN etd-0629117-234517
Author Hsin-yun Hsu
Author's Email Address No Public.
Statistics This thesis had been viewed 5385 times. Download 0 times.
Department Applied Mathematics
Year 2016
Semester 2
Degree Master
Type of Document
Language English
Title Improving the search of near-optimal solution of vehicle routine problems with parallelable modified algorithms
Date of Defense 2017-06-29
Page Count 47
Keyword
  • Feiring algorithm
  • Vehicle routing problem (VRP)
  • MPI
  • Travelling salesman problem (TSP)
  • k-mean clustering
  • 2-opt
  • Abstract We consider finding the near-optimized solution of logistic's vehicle routing problem includes grouping of customers and travelling salesman problem.
          We try to balance the number of customers for each vehicle. According to k-mean clustering algorithm, we add restrictions of the number of each cluster and conditions of distributing each customer to achieve our target.
          After that, we want to find a near-shortest route passing through all the customers for each cluster. This problem is a travelling salesman problem, has been proved to be an NP-hard problem that exact solution should be got by exhaustion method or branch and bound method. Therefore, we use Diagonalize Complete Algorithm to construct a feasible Hamiltonian path, and then using 2-opt and Feiring algorithm to get a shorter path. Among these algorithm, if the number of cluster is n, then the computing of $2$-opt algorithm is O( n^2 ) and can not be parallelable, so we consider two different way to modify the algorithm to do parallel computing with MPI. That is, if we use p processes in MPI, then it can reducing the computing to O( n^2/p ).
    Advisory Committee
  • Tzon-Tzer Lu - chair
  • Tsung-Lin Lee - co-chair
  • Peng-Jen Lai - co-chair
  • Chieh-Sen Huang - advisor
  • Files
  • etd-0629117-234517.pdf
  • Indicate in-campus at 99 year and off-campus access at 99 year.
    Date of Submission 2017-08-02

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys