1000分讨论客户管理之一：最优路径 （请吕雪松和关心客户管理的人捧场！） (100分)

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-28

• #1

我计划在我的项目中加入客户管理，客户的地址在地图重要有体现，要有
最优路径的算法（当然包括费用、最快路径、最短路径），显示某个地区的客户密度（用
颜色的深浅），品牌影响力的大小（等等相关影响力），维修影响力的大小、富裕程度、
对手影响力。这样有利于决策。还有，mapinfo有没有中文版的下载？

有好的建议的有重分！

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-29

• #2

你的需求是一个典型的GIS空间引力模型。
介绍你几个站点看看吧,希望你的问题能具体一点,我们才更容易交流.

http://www.3cn.com.cn/sbs/article/54/554.jhtml
http://www.sutpc.com/ytdsjt/tszs/jtghyjs/%E5%9F%8E%E5%B8%82%E5%9C%9F%E5%9C%B0%E5%88%A9%E7%94%A8%E4%B8%8E%E4%BA%A4%E9%80%9A%E7%BB%BC%E5%90%88%E8%A7%84%E5%88%92%E7%A0%94%E7%A9%B6.htm
http://www.cooltang.com/box/200111/2001112910130000611372332058369.htm

ArcLogistics用过吗,对你有帮助的.

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-29

• #3

to 吕雪松
谢谢关注，我的需求是这样的，现在有一个城市的地图包括路径，有详细的客户地址。
详细的地址可能是在地图的某个区域。当同时有n个地址要求送货，可以分成m（m<n ）
次送货，那么费用最小的路径(指总路径最短的)、总耗时最小的路径如何解？
空间引力模型是说的第二个问题，确定个引力的权，当引力出现真空时只要有连锁店就
可以获得收益，但是如何知道不同引力作用下的开始分公司（连锁）最好的地点？

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-30

• #4

没人捧场？

 

C

cfx

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-30

• #5

我也正在准备做GIS
的项目知道关于这方面有哪些好的站点??

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-04

• #6

在北京出差，不好意思。
你的第一个问题，是物流中的经典问题，如果是一辆车进行N条路线配送那还好，如果是多
车多路线求最优解，就比较麻烦了。我目前还没有很好的算法，不过我是觉得这里面有两个
矛盾：数据的不精确性和求最优解之间的矛盾；求出来的最优解同实际运输过程中的不确定
因素之间的矛盾。因此，求Greedy解就可以了。

以前看ArcLogisitcs中有这个算法，很感兴趣，但因项目原因中途而止，这个问题我准备
重新研究一下，大家多关注，多交流。

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-05

• #7

谢谢吕大侠！！！！！！
ArcLogisitcs有down的地方吗？算法如何实现那？
就客户需求来说，不止是多辆车，而且货物可能还没有分配。不如先讨论一下一辆车的问题，
我看这点分数太少了，就这个问题讨论完，我在另开几个吧，用1000分讨论个明白吧。
我想吕大侠说的矛盾也使我困惑，一些关键性参数是变量。这就需要分类讨论，将能出现的
类别分讨论,也只有这样才能真正了解相关算法，而不是仅仅解决了一个问题。
本来我对GIS很陌生，看到人气不旺才来根据我所碰到的问题引申开来提问，如果象吕大侠
这样高朋满天的DFW提出问题来，效果肯定不一般，分数我可以加倍奉还。我想我们应该在
算法上多下功夫，而不要拘泥于技巧、程序。

 

D

dongliu

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-05

• #8

ArcLogisitcs有down的地方吗？算法如何实现那？
xiexie

 

P

proman

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-08

• #9

关注，我过1个月也要做这方面的分析。先听听大家的讨论。

 

B

barton

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #10

这问题提得真是好！

 

Y

yyanghhong

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #11

I haddo
ne a project that is similar to this one, that is for calulating the balance of
the electrical system. the way I adopted is building the link of each object in the map.
then
using the recursive to search the route.

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #12

to yyanghhong, 能说说你的思路吗？具体一点，如何求得最短或者最快（加权）的路径？
抵归如何设计？是遍历吗？

 

Y

yyanghhong

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #13

the topology of map. you can convert a map to a tree by fixing a start point.
then
figure out the distance of route according to the length of each branch of tree.

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #14

to yyanghhong：
谢谢你的关注！！！这个办法似乎可行，可是如果路径很多就不行了，效率如何保证？何况
还有若干个货物，每个货物地址都是不同的。你的思路……好像还差一点，能不能在进一步？

 

C

CJF

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #15

其实在没有最好的方法下，可以用最蠢的办法，就是老老实实的一个个计算，然后，再
看情况进行舍弃，就可以提高效率了。。[]

 

Y

yyanghhong

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #16

the better way is developing a service that is runing at intervals, it can search the
route and store it into a index database. other application get the data through
checking the index database. just like a search engine

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #17

to CJF：
兄弟，谢谢关心！不过要是象你说的那样，我还问个什么劲，有好的方案的话欢迎讨论，
没有的话帮忙提前，谢谢。
to yyanghhong,：
你能用中文输入吗？我看的实在费劲。最短路径的问题就不要讨论了，算法书上都有，关键
是多个货物一辆车，如何运输路径最短。

 

C

CJF

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-09

• #18

不是的。。。

或许你不明白我说的舍弃。我指的是在算法过程中，进行对情况、路径等环境的预测，
根据情况，实现对当前的路径进行舍弃等操作，然后立即进行下一路径的预测等操作，
从而有效的加快程序的运行效率。

可以说，是对当前的算法的优化，实现效率的提高。。

其实，在没有新的算法的情况下，优化还是提供效率的一大办法。。。[]

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-10

• #19

这有赖于你的基础数据的良好的拓扑关系。如果是plain data，那么你的计算量是非常大，
且，不一定准确。

可以去参考日本导航协会的基于空间四叉树的kiwi数据格式。这是我目前见过最优化的
路径拓扑结构了。

 

T

t1122

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-01-11

• #20

to CJF：
你说的是有道理，我也想过，先将一些比当前最小的长的路径去掉，就像最短距离一样
不过事实上路径太多，可能走的路径有很多条，这样算起来即使优化后遍历（或回溯）也很难实现。
吕大侠说得很有道理，有时候我们专注在算法里，没有考虑过拓扑结构的问题，不知道你有没有这方
面的资料？很希望你和吕大侠能用你们的号召力，提出一些好问题来（最好是我想知道的），分数由
我来出，4000分以内的我还是可以办得到。比如我的问题，可能不是一般的程序员能解决的了的。
其实这个问题有变通的办法，只是我想把它弄个明白。

to 吕大侠：
吕大侠古道热肠，非常感谢。我是想这样设计数据库：PNameS、PNameE：最小区间（没有岔路的
路径）两个交点(顶点)的名称；PLen：长度。这是基本量表，还有一个就是记录最常用的路径（到一个
地区）的长度。可是这个结构针对两点之间最短距离有效，对送货问题没有什么帮助。我想能不能通过
图形来求得最短距离？在通过加权来计算最短时间？如果要设计数据库，有什么好的方案吗？