Skip to content

Latest commit

 

History

History
93 lines (65 loc) · 3.52 KB

README.md

File metadata and controls

93 lines (65 loc) · 3.52 KB
Raw

LOOPTSP

Problem for EBA Virtual Internship2018.

Problem Setting

This problem is based on TSP (Traveling Salesman Problem).

A container ship leaves a port and returns to the port after touching all given ports Ideal navigation dates of all each two ports are given, but actual navigation dates changes due to some trouble (In real world, the delay caused by weather condition) In this problem, the actual navigation dates (Actual(Dep, Arr)) are defined the following:

  • ElpsedDateInDepPort: Integrating dates from first port on departing port
  • Ideal(Dep, Arr): Ideal navigation dates from Dep (Depareture port) to Arr (Arrival port)
  • Actual(Dep, Arr) = Ideal(Dep,Arr) + ElpsedDateInDepPort % Ideal(Dep,Arr)
  • # "%" means modulo operator

Find voyage route whose integrating date is smallest

Example

In this example, ideal dates are defined as following table, whose content is same as "data/sample/cost.csv." And, start port is given as "TOKYO."

TOKYO OSAKA NAGOYA SHANGHAI LONG_BEACH SEATTLE
TOKYO - 4 2 8 24 22
OSAKA 4 - 2 6 26 24
NAGOYA 2 2 - 8 24 22
SHANGHAI 8 6 8 - 28 26
LONG_BEACH 24 26 24 28 - 4
SEATTLE 22 24 22 26 4 -

When a ship touchs ports in order "TOKYO(start) -> OSAKA -> NAGOYA -> SHANGHAI -> LONG_BEACH -> SEATTLE -> TOKYO," final integrating dates (Elpased dates) is 100 and the detail is the following.

Port Elpased dates Arrival Port Navigation Dates
TOKYO (Start port) 0 OSAKA 4 (4 + 0%4)
OSAKA 4 NAGOYA 2 (2 + 4%2)
NAGOYA 6 SHANGHAI 14 (8 + 6%8)
SHANGHAI 20 LONG_BEACH 48 (28 + 20%28)
LONG_BEACH 68 SEATTLE 4 (4 + 68%4)
SEATTLE 72 TOKYO 28 (22 + 72%22)
TOKYO 100

Submissions

Results of Planning

Ideal date file for actual setting is "data/cost.csv."

Please, submit voyage plans whose start ports are the follwing and "Elapsed dates" of these plans.

  • TOKYO
  • OSAKA
  • SEATTLE
  • HONGKONG
  • THURSDAY_ISLAND

A format example is "data/sample/voyage_plan.txt."

The submission file name of each start port is "'START_PORT_NAME'_voyage_plan.txt", like "TOKYO_voyage_plan.txt."

If you can find optimum solution, you will tackle extra problem, "data/extra_problem_cost.csv." (in preparation)

Description for Algorithm

Scripts

CUI

This repository has cui based tiral environment. The enviroment starts by following command. (python3)

PYTHONPATH=./looptsp/ python looptsp/looptsp_cui.py data/sample/cost.csv "TOKYO"

Loading Voyage Plan

This repository has a script, which reads a voyage plan file. The script executes by folloing command.

PYTHONPATH=./looptsp/ python looptsp/looptsp_file_input.py data/sample/cost.csv 'TOKYO' data/sample/voyage_plan.txt

And, the script outputs.

Total date is 80

So, the plan is different from the above example and the total dates is also different.