LoginSignup
46
45

More than 5 years have passed since last update.

フューチャーアーキテクトAdvent Calendar 2015Day 1
@ma91n(junki mano)inフューチャー株式会社

行き先がめちゃくちゃ多くても大丈夫。jspritで効率よく目的地を回っちゃおう

Last updated at Posted at 2015-11-30

はじめに

休日をリア充すべく、色々なところに遊びに行きたいですよね。
どういう順番で回れば良いでしょうか？
現実的には行き先がどんな場所か（体力を使うか、ゆっくりするか、混んでいるか）など気分的に考えて
スケジューリングしますが、今回は一番移動距離（時間）が少なくなる順番を求めてみます。

巡回セールスマン問題

巡回セールス問題とは、複数の都市をどの順序で回れば一番総距離が短くなるか？という非常に有名な問題です。
都市の数が大きくなると計算量が莫大になるので、有限時間で処理が終わらないのが難しいポイントだと言われています。
計算複雑性理論では「NP困難」とも言われるそうです。

巡回セールスマン問題はよく下図のようなグラフで表現されます。
「頂点」に行き先、「辺」に距離（時間）が描かれており、全ての頂点を周りかつ辺の合計が最小になる順序を得ることががゴールですね。
図3.png

今回色々なところに遊びに行きたいのですが、はて困りました。
色々な行き先を最短経路で回りたい…。これは巡回セールス問題です。
どうしましょう。

jspritを利用する

jsprit.png

jspritはJavaで実装されたOSSのライブラリです。
巡回セールスマン問題(Traveling Salesman Problem: TTSP)だけではなく、車両ルーティング問題(Vehicle Routing Problems :VRP)という複数の車両で荷物をどう運べば良いかといった物流系の最適化にも用いることが出来ます。

本家サイトはこちら。
https://jsprit.github.io/

ソースはこちらです。
https://github.com/jsprit/jsprit

jspritはメタヒューリスティクスという最適な解ではないけれど実際には良い解を、現実的な時間で求めるというアプローチを採用しているため、非常に高速に動作します。
（2000ノードくらいでも2-3時間くらいで終わりましたので十分優秀かと思います）

機能は非常にリッチで、上記のグラフでは表現されていませんが、例えば「F」の頂点に
12:00～13:00の時間帯で到着すること、といった条件も追加することが出来ます。
さらにVRPの利用で、車両の積載容量を意識した荷物の配達・集荷や、利用する車種に制約を設定することも出来ます。

セットアップ

Maven Central Repositoryにはアップロードされていないのでご注意を。
Githubのリポジトリ機能を利用して管理しているようです。

最新を利用したかったので下記サンプルではsnapshotsからJARを取得します。
snapshot無しバージョンを利用したい場合はrepositoryのURLをhttps://github.com/jsprit/mvn-rep/raw/master/releasesに書き換えればOKです。
現在の最新バージョンは1.6.1です。（2015/11/31時点）

pom.xml
    <dependencies>
        <!-- 安定版がいい人は1.6.1に -->
        <dependency>
            <groupId>jsprit</groupId>
            <artifactId>jsprit-core</artifactId>
            <version>1.6.2-SNAPSHOT</version>
        </dependency>
        <dependency>
            <groupId>jsprit</groupId>
            <artifactId>jsprit-analysis</artifactId>
            <version>1.6.2-SNAPSHOT</version>
        </dependency>
        <dependency>
            <groupId>jsprit</groupId>
            <artifactId>jsprit-instances</artifactId>
            <version>1.6.2-SNAPSHOT</version>
        </dependency>
    </dependencies>

    <!-- リポジトリ設定 -->
    <!-- 安定版がいい人はurlを書き換える -->
    <repositories>
        <repository>
            <id>jsprit-snapshots</id>
            <url>https://github.com/jsprit/mvn-rep/raw/master/snapshots</url>
        </repository>
    </repositories>

利用方法

基本形

Wikiのトップに載っている基本形です。
もともとが車両ルーティング問題を解くためのライブラリのため、車両自体の設定があって見苦しいですがご容赦を… :disappointed_relieved:

コードの大まかな流れを説明します。

  1. 出発位置の設定
  2. 行き先の設定（setLocationでX/Y座標を設定）
  3. 複数個の解を求めて、一番良い解を取得し結果出力

結果出力はアスキーアートやpng画像形式は存在しますが、シンプルなCSV形式などは標準では含まれていないようです。
そのためCSVにファイル出力させたい場合は、SolutionPrinter.printの実装を参考に独自実装が必要そうです。

基本形Main.java
import jsprit.analysis.toolbox.GraphStreamViewer;
import jsprit.analysis.toolbox.Plotter;
import jsprit.core.algorithm.box.Jsprit;
import jsprit.core.problem.Location;
import jsprit.core.problem.VehicleRoutingProblem;
import jsprit.core.problem.job.Service;
import jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import jsprit.core.problem.vehicle.VehicleImpl;
import jsprit.core.problem.vehicle.VehicleType;
import jsprit.core.problem.vehicle.VehicleTypeImpl;
import jsprit.core.reporting.SolutionPrinter;
import jsprit.core.reporting.SolutionPrinter.Print;
import jsprit.core.util.Solutions;

public class Main {

    private static final int WEIGHT_INDEX = 0;

    public static void main(String[] args) {

        // 車両の種類を設定（純粋な巡回セールスマン問題として用いる場合は適当で良い）
        // newInstanceの引数は一意にする必要があります
        VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance("vehicleType")
            .addCapacityDimension(WEIGHT_INDEX, Integer.MAX_VALUE)
            .build();

        // 開始位置を設定
        // newInstanceの引数は一意にする必要があります
        VehicleImpl vehicle = VehicleImpl.Builder.newInstance("vehicle")
            .setStartLocation(Location.newInstance(10, 10))
            .setType(vehicleType)
            .build();

        // 行き先を設定
        // newInstanceの引数は一意にする必要があります
        Service service1 = Service.Builder.newInstance("1")
            .addSizeDimension(WEIGHT_INDEX, 1)
            .setLocation(Location.newInstance(5, 7))
            .build();
        Service service2 = Service.Builder.newInstance("2")
            .addSizeDimension(WEIGHT_INDEX, 1)
            .setLocation(Location.newInstance(5, 13))
            .build();
        Service service3 = Service.Builder.newInstance("3")
            .addSizeDimension(WEIGHT_INDEX, 1)
            .setLocation(Location.newInstance(15, 7))
            .build();
        Service service4 = Service.Builder.newInstance("4")
            .addSizeDimension(WEIGHT_INDEX, 1)
            .setLocation(Location.newInstance(15, 13))
            .build();
        Service service5 = Service.Builder.newInstance("5")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(6, 3))
                .build();
        Service service6 = Service.Builder.newInstance("6")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(10, 3))
                .build();
        Service service7 = Service.Builder.newInstance("7")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(4, 6))
                .build();
        Service service8 = Service.Builder.newInstance("8")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(1, 5))
                .build();
        Service service9 = Service.Builder.newInstance("9")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(8, 8))
                .build();
        Service service10 = Service.Builder.newInstance("10")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(9, 2))
                .build();
        Service service11 = Service.Builder.newInstance("11")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(10, 14))
                .build();
        Service service12 = Service.Builder.newInstance("12")
                .addSizeDimension(WEIGHT_INDEX, 1)
                .setLocation(Location.newInstance(12, 13))
                .build();

        // 問題（グラフ）を構築
        VehicleRoutingProblem problem = VehicleRoutingProblem.Builder.newInstance()
            .addVehicle(vehicle)
            .addJob(service1)
            .addJob(service2)
            .addJob(service3)
            .addJob(service4)
            .addJob(service5)
            .addJob(service6)
            .addJob(service7)
            .addJob(service8)
            .addJob(service9)
            .addJob(service10)
            .addJob(service11)
            .addJob(service12)
            .build();

        // 問題に対するアルゴリズムを取得し、解を求める
        Collection<VehicleRoutingProblemSolution> solutions = Jsprit.createAlgorithm(problem)
            .searchSolutions();

        // 一番結果が良かった解を求める
        VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

        // [結果の出力]
        // 1. 標準出力
        SolutionPrinter.print(problem, bestSolution, Print.CONCISE);

        // 2. png形式で出力
        new Plotter(problem, bestSolution).plot("result/solution.png", "solution");

        // 3. swing/awtで出力
        new GraphStreamViewer(problem, bestSolution).setRenderDelay(500).display();
    }

}

基本形の結果

GraphStreamViewerの結果は以下のように動的に動いてくれます。
ちょっとだけ面白いですね。
jobsというのが行き先で12個、costsというのが総距離です。

out.gif

また、コンソールにはアスキーアートで表出力されます。
サマリ情報だけですね。

（略）
2015-12-01 11:00:32,606 [main] INFO  jsprit.core.algorithm.VehicleRoutingAlgorithm$Counter - iterations 1024
2015-12-01 11:00:32,949 [main] INFO  jsprit.core.algorithm.VehicleRoutingAlgorithm - iterations end at 2000 iterations
2015-12-01 11:00:32,949 [main] INFO  jsprit.core.algorithm.VehicleRoutingAlgorithm - took 0.877 seconds
+--------------------------+
| problem                  |
+---------------+----------+
| indicator     | value    |
+---------------+----------+
| noJobs        | 12       | 
| noServices    | 12       | 
| noShipments   | 0        | 
| fleetsize     | INFINITE | 
+--------------------------+
+----------------------------------------------------------+
| solution                                                 |
+---------------+------------------------------------------+
| indicator     | value                                    |
+---------------+------------------------------------------+
| costs         | 49.09801566050274                        | 
| noVehicles    | 1                                        | 
| unassgndJobs  | 0                                        | 
+----------------------------------------------------------+

どういう順序かという情報が欲しい場合（普通はそうですよね :sweat_smile: ）、SolutionPrinter.printの第三引数をPrint.VERBOSEにすれば良いです。
SolutionPrinter.print(problem, bestSolution, Print.VERBOSE);

そうすると以下のようにより詳しい情報が出力されます。

（略）
2015-12-01 11:12:26,331 [main] INFO  jsprit.core.algorithm.VehicleRoutingAlgorithm - took 0.696 seconds
+--------------------------+
| problem                  |
+---------------+----------+
| indicator     | value    |
+---------------+----------+
| noJobs        | 12       | 
| noServices    | 12       | 
| noShipments   | 0        | 
| fleetsize     | INFINITE | 
+--------------------------+
+----------------------------------------------------------+
| solution                                                 |
+---------------+------------------------------------------+
| indicator     | value                                    |
+---------------+------------------------------------------+
| costs         | 49.09801566050274                        | 
| noVehicles    | 1                                        | 
| unassgndJobs  | 0                                        | 
+----------------------------------------------------------+
+--------------------------------------------------------------------------------------------------------------------------------+
| detailed solution                                                                                                              |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| route   | vehicle              | activity              | job             | arrTime         | endTime         | costs           |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | vehicle              | start                 | -               | undef           | 0               | 0               |
| 1       | vehicle              | service               | 2               | 6               | 6               | 6               |
| 1       | vehicle              | service               | 11              | 11              | 11              | 11              |
| 1       | vehicle              | service               | 12              | 13              | 13              | 13              |
| 1       | vehicle              | service               | 4               | 16              | 16              | 16              |
| 1       | vehicle              | service               | 3               | 22              | 22              | 22              |
| 1       | vehicle              | service               | 6               | 29              | 29              | 29              |
| 1       | vehicle              | service               | 10              | 30              | 30              | 30              |
| 1       | vehicle              | service               | 5               | 33              | 33              | 33              |
| 1       | vehicle              | service               | 8               | 39              | 39              | 39              |
| 1       | vehicle              | service               | 7               | 42              | 42              | 42              |
| 1       | vehicle              | service               | 1               | 43              | 43              | 43              |
| 1       | vehicle              | service               | 9               | 46              | 46              | 46              |
| 1       | vehicle              | end                   | -               | 49              | undef           | 49              |
+--------------------------------------------------------------------------------------------------------------------------------+

拡張したい

今回はノード情報をそのままjspritに設定しているので、例えばID1→ID2へは移動させたくない、といった制約を付けていません。
その場合は標準では対応できず、AbstractForwardVehicleRoutingTransportCostsクラスを拡張する必要があります。
拡張に関してはjsprit.core.util.EuclideanCostsを参考にすると良いと思います。

拡張例

通行不可の辺を作りたい（A地点→B地点の移動は許可しない、B地点→A地点は許可する）場合の拡張例を下記に示します。
ExtendedForwardVehicleroutingTransportCostsはaddメソッドで禁止したい行き先をFrom→Toで設定することが出来ます。

jsprit拡張
package com.github.jsprit;

import java.util.HashMap;
import java.util.Map;

import jsprit.core.problem.Location;
import jsprit.core.problem.cost.AbstractForwardVehicleRoutingTransportCosts;
import jsprit.core.problem.driver.Driver;
import jsprit.core.problem.job.Service;
import jsprit.core.problem.vehicle.Vehicle;
import jsprit.core.util.Coordinate;
import jsprit.core.util.EuclideanDistanceCalculator;

public class ExtendedForwardVehicleroutingTransportCosts extends AbstractForwardVehicleRoutingTransportCosts {

    private Map<Location, Location> forbiddenEdge = new HashMap<>();

    public void add(Service from, Service to) {
        forbiddenEdge.put(from.getLocation(), to.getLocation());
    }

    @Override
    public double getTransportCost(Location from, Location to, double time, Driver driver, Vehicle vehicle) {

        double distance = calculateDistance(from, to);

        double costs = distance;
        if (vehicle != null && vehicle.getType() != null) {
            costs = distance * vehicle.getType().getVehicleCostParams().perDistanceUnit;
        }
        return costs;
    }

    @Override
    public double getTransportTime(Location from, Location to, double time, Driver driver, Vehicle vehicle) {
        double distance = calculateDistance(from, to);
        return distance;
    }

    /**
     * 直線距離ではなく、三角関数を利用した計算・GoogleMapを利用したい場合はここを拡張する
     */
    private double calculateDistance(Location fromLocation, Location toLocation) {
        Coordinate from = fromLocation.getCoordinate();
        Coordinate to = toLocation.getCoordinate();

        if (from == null || to == null) {
            throw new NullPointerException("fromLocation or toLocation is null");
        }

        Location value = forbiddenEdge.get(fromLocation);
        if (value != null && value.equals(toLocation)) {
            // 禁止辺（方向あり）に一致した場合はDoubleの最大値を返し現実的に利用しないようにする
            return Double.MAX_VALUE;
        }

        // 通行可能な場合は直線距離を計算します
        // （三角関数やGeocoding的なルーティングを行う場合は以下のEuclideanDistanceCalculator.calculateDistanceの部分を書き換えます）

        // --------------- TODO ココを拡張---------------
        return EuclideanDistanceCalculator.calculateDistance(from, to);
        // ------------------------------

    }

}

今回はservice5→Service8のルートを禁止にします。
拡張したクラスは以下のようにVehicleRoutingProblem.Builderのインスタンスに設定すればOKです。

jsprit拡張の呼び出し方
    // 拡張クラスのインスタンスを生成
    ExtendedForwardVehicleroutingTransportCosts costs = new ExtendedForwardVehicleroutingTransportCosts();
    // 禁止にしたい辺を設定（複数可）
    costs.add(service5, service8);

    // 問題（グラフ）を構築
    VehicleRoutingProblem problem = VehicleRoutingProblem.Builder.newInstance()
      .setRoutingCost(costs)
      .addVehicle(vehicle)
      .addJob(service1)
      .addJob(service2)
      .addJob(service3)
      .addJob(service4)
      .addJob(service5)
      .addJob(service6)
      .addJob(service7)
      .addJob(service8)
      .addJob(service9)
      .addJob(service10)
      .addJob(service11)
      .addJob(service12)
      .build();

拡張の結果

基本形とルートが変わりましたね。
総コストも49.09801566050274から49.098015660502746とほんの僅かですが、結果が悪くなっています。
制約が増えたので一番良い組み合わせを採択出来なかったのだと思います。

233.gif

おまけ

IntelCore i5のプロセッサでは2000ノードくらいで2-3時間くらい処理がかかりました。
百ノード程度であれば1分以内に処理が終わります。
これで行き先が多くても休日を有意義に過ごすことが出来ます。
めでたし、めでたし。

他のルーティングライブラリ

教科書にのっているくらい有名な問題なのでもっと種類があるかと思いましたが、探し方が悪いのか
あまり見当たりませんでした。
とくに日本語の記事は少ないですね…。

hisper4j

hipster-logo-text.png
http://www.hipster4j.org/
heuristic
サイトが一番イケている感じなので次に試してみる予定です。
純粋に巡回セールスマン問題を解くならこちらの方が適切な気がします。

OptaPlanner

optaPlannerLogo200px.png
http://www.optaplanner.org/
日本語記事が唯一（？）見受けられたもの。

Open-VRP

11.png
http://openvrp.com/
PostgreSQL/PostGISへのビルトイン形式

vroom

vroom.png
https://github.com/jcoupey/vroom
http://slideplayer.com/slide/4916092/
C++14
VRP

46
45
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
46
45