Neo4j的 - 旅行商 [英] Neo4J - Traveling Salesman

问题描述

我试图解决使用图形数据库的扩充TSP问题，但我挣扎。我很伟大的SQL，但我对暗号共小白。我创建与城市（节点）和航班（关系）的简单图形。

I'm trying to solve an augmented TSP problem using a graph database, but I'm struggling. I'm great with SQL, but am a total noob on cypher. I've created a simple graph with cities (nodes) and flights (relationships).

的设置：旅行到8个不同的城市（每周1个城市，没有重复），最低的总飞行成本。我试图解决的最佳路径，以尽量减少的航班，每周从而改变了成本。

THE SETUP: Travel to 8 different cities (1 city per week, no duplicates) with the lowest total flight cost. I'm trying to solve an optimal path to minimize the cost of the flights, which changes each week.

这里是一个引擎收录文件包含我的节点和放大器;关系。只要运行它反对Neo4JShell插入的数据。

Here is a file on pastebin containing my nodes & relationships. Just run it against Neo4JShell to insert the data.

我开始使用这篇文章为基础，但它不处理不断变化的距离（或在我的情况下飞行费用）

I started off using this article as a basis but it doesn't handle the changing distances (or in my case flight costs)

我知道这在语法上是可怕的/不可执行的，但这里是我做了什么至今让只有两个航班;

I know this is syntactically terrible/non-executable, but here's what I've done so far to get just two flights;

MATCH（A：CITY） - [F1：飞行{一周：1}] - ＆GT;（二：CITY） - [F2：飞行{周：2}] - ＆GT;（三：市） 返回，B，C;

MATCH (a:CITY)-[F1:FLIGHT{week:1}]->(b:CITY) -[F2:FLIGHT{week:2}]->(c:CITY) RETURN a,b,c;

但是，这并不运行。

接下来，我想我只是试图找到所有的城市和放大器;从一周的航班，但它不工作的权利无论是作为我得到的航班，其中每周＆LT;> 1，以及= 1

Next, I thought I'd just try to find all the cities & flights from week one, but it's not working right either as I get flights where week <> 1 as well as =1

MATCH（n），其中（N） - [：飞行{一周：1}] - ＆GT;（）返回否

谁能帮帮忙？

PS - 我没有结婚用图形数据库来解决这个问题，我刚刚看了一下他们，并认为这将是非常合适的去尝试，再加上给了我与他们合作的理由，但如此到目前为止，我没有多少（或有）成功。

PS - I'm not married to using a graph DB to solve this, I've just read about them, and thought it would be well fitted to try it, plus gave me a reason to work with them, but so far, I'm not having much (or any) success.

推荐答案

Neo4j的可能是罚款的软件，但我不希望它成为解决这一NP难问题有很大帮助。相反，我想指出你的整数规划解算器（这个，也许，但我不能保证它）建议你提出这个问题。作为一个整数的程序如下：

neo4j may be a fine piece of software, but I wouldn't expect it to be of much help in solving this NP-hard problem. Instead, I would point you to an integer program solver (this one, perhaps, but I can't vouch for it) and suggest that you formulate this problem as an integer program as follows.

有关每个航班 F ，我们创建了一个0-1变量 X（F）是1，如果航班 F 取0，如果航班 F 不采取。我们的目标是要的航班的总成本最小化（我会假设每个购买的是一个独立的决定;如果没有，那么你有一些更多的工作要做）。

For each flight f, we create a 0-1 variable x(f) that is 1 if flight f is taken and 0 if flight f is not taken. The objective is to minimize the total cost of the flights (I'm going to assume that each purchase is an independent decision; if not, then you have some more work to do).

minimize sum_{flights f} cost(f) x(f)

现在我们需要一些约束。每个星期，我们购买的只有一个航班。

Now we need some constraints. Each week, we purchase exactly one flight.

for all weeks i, sum_{flights f in week i} x(f) = 1

我们可以只在一个地方的时间，所以如果我们飞入城市 v 一星期我 ，那么我们就飞出去城市 v 的一周 I + 1 。我们EX preSS这个约束与一个陌生又地道的线性方程。

We can be in only one place at a time, so if we fly into city v for week i, then we fly out of city v for week i+1. We express this constraint with a strange but idiomatic linear equation.

for all weeks i, for all cities v,
  sum_{flights f in week i to city v} x(f) -
    sum_{flights f in week i+1 from city v} x(f) = 0

我们可以飞入每个城市最多一次。我们可以飞出每个城市最多一次。这就是我们如何执行访问一次的约束。

We can fly into each city at most once. We can fly out of each city at most once. This is how we enforce the constraint of visiting only once.

for all cities v,
  sum_{flights f to city v} x(v) <= 1

for all cities v,
  sum_{flights f from city v} x(v) <= 1

我们就要完成了。我将承担在这一点上的旅程开始和结束在家居城 U 提前知道。对于第一个星期，删除 U 未出发的所有航班。对于上周，删除未到达 U 的所有航班。整数规划的灵活性，然而，意味着它很容易使其他安排。

We're almost done. I'm going to assume at this point that the journey begins and ends in a home city u known ahead of time. For the first week, delete all flights not departing from u. For the last week, delete all flights not arriving at u. The flexibility of integer programming, however, means that it's easy to make other arrangements.

这篇关于Neo4j的 - 旅行商的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！