- Hi,

Yes, ¡®Vehicle route problem¡¯ is a search problem. It is a central

problem in distribution management. The classical problem¡¯s

description is:

Fact:

1. brief:

a) One company has many customers for distribution products.

The company has many vehicles fore doing the work. Every customer¡¯s

order is small. Company wants to design a plan for all vehicles to

lower the distribution cost.

2. details:

a) G = (V,E) be an undirected graph where V = {v0,v1,¡vn} is

a set of vertices representing customers. E ={(vi,vj)|vi,vj belong to

V, i<j} is the edge set.

b) Vertex v0 denotes a depot at which are based m identical

vehicles of capacity Q, where m is a decision variable or a constant.

c) Each customer of V\{v} has a non-negative demand qi, a non-

negative service time si. (waiting, unloading time)

d) A distance matrix (cij) is defined on E. We use the terms

distance and travel time interchangeably.

Problem(VRP---for vehicle route problem

1. designing a set of m vehicles routes having a minimum total

length and such that

a) each route start and ends at the depot

b) each remaining city is visited exactly once by one vehicle

c) the total demand of a route does not exceed

d) The total duration of a route does not exceed a preset

limit L.

Many people think that the core of VRP is TSP (traveling salesman

problem). But it is more difficult than TSP. TSP has only one

salesman.

Many variants of VRP exists,

1. To delete the above fact b. Some customer¡¯s order is very

big so that the order is more than the vehicle¡¯s capacity.

2. Another special vertex appears. It is not customer. It is

highway fee collection point. Therefore the Problem-1 requirement

should be modified.

3. Many different kind of vehicle exists, For example, one

kind of vehicles are for freezing products, one kind of vehicles are

for common products.

4. Every vehicle can have more than 1 route.

5. etc.

There are many different approachs to solve the problem:

1. hill climbing

2. simulated annealing

3. neural network

4. GA

5. ant system

6. etc

I think many knowledge of AIMA can be applied to this problem, and

this problem¡¯s requirement is easy to imagine and new requirement

can be added for more difficulty.

Thank you for your attention.

Best regards/chenyu (shanghai, China)

--- In aima-talk@yahoogroups.com, setiawan adhiputro <sea12_02@y...>

wrote:> this "Vehicle route problem", is that about searching problem?

complex depending on the requirement.

>

> E etech058 <etech058@o...> wrote:Hi,

> My proposal is "Vehicle route problem". The problem can be easy or

>

______________________________________________________________________

>

> Best regards/chenyu

>

> -----Original Message-----

> From: AMANULLAH NURULLAH [mailto:amanumr@y...]

> Sent: 2004Äê3ÔÂ11ÈÕ 23:11

> To: aima-talk@yahoogroups.com

> Subject: [aima-talk] Project ideas!

>

> Hi, i am taking an AI class with AIMA as text and

> planning for a mini course project.

>

> Any ideas, suggestions?

>

> aman

>

>

__> Yahoo! India Insurance Special: Be informed on the best policies,

services, tools and more.

> Go to: http://in.insurance.yahoo.com/licspecial/index.html

Service.

>

>

>

>

> Yahoo! Groups Links

>

>

>

>

>

>

> ---------------------------------

> Yahoo! Groups Links

>

> To visit your group on the web, go to:

> http://groups.yahoo.com/group/aima-talk/

>

> To unsubscribe from this group, send an email to:

> aima-talk-unsubscribe@yahoogroups.com

>

> Your use of Yahoo! Groups is subject to the Yahoo! Terms of

>

>

>

> Do you Yahoo!?

> Yahoo! Mail - More reliable, more storage, less spam - Hello,

I have asked others to help me to translate it from Japanese

language. But it make me dispointed because it doesn't contain any

information about how to learning. This documents mainly discuss the

software "Mr.Log"'s brief information. This software use "TS (tubu

search)" and "SA(simulated annealing)" to solve the problem.

But after comparing many algorithm (methodology), I have decided to

use multi-agents (trading algorithm) to do my VRP project.

For GUI and data management, to use mapinfo.

If you are interested in VRP and want to make project on it. The

following paper may be useful to you.

1. about mapinfo and VRP

It contains some "machine learning" algorithm, but it doesn't say

details.

==========================

magazine: journal of operational research society

August 2002, Volume 53, Number 8, Pages 842-854

Map-Route: a GIS-based decision support system for intra-city vehicle

routing with time windows

G Ioannou, M N Kritikos and G P Prastacos

Athens University of Economics and Business, Athens, Greece

Correspondence to: G Ioannou, Management Sciences Laboratory,

Graduate Program in Decision Sciences, Department of Management

Science and Technology, Athens University of Economics and Business,

8th Floor, 47A Evelpidon Street and 33 Lefkados Street, Athens 113-

62, Greece. E-mail: ioannou@...

2. multi-agent truck==========================

http://citeseer.ist.psu.edu/455751.html

It shows why multi-agent method is better. It makes the system more

flexible and easy for adding more constraint.

Thank you for your attention.

kind regarsd

chenyu

--- In aima-talk@yahoogroups.com, ³ÂÓí <chenyu468@y...> wrote:

> Hi,

> I have found a introduction which is about VRP as a learning

problem.

> But it is written in Japanease, I can't understand it now. After

> asking helping others for translation, I could reply you later.

>

> The website: http://citeseer.ist.psu.edu/

> contains many paper about VRP. Maybe keyword of "learning VRP" will

> help you found many similars.

>

>

>

> In addition, I found some useful maganizes about this problem. I

have

> found them in my local library (shanghai library). Maybe you could

> find them in your locals too.

> 1. JORS (Journal of the Operation Research)

> ISSN: 0160-5682

>

> 2. Annals of Operational Research

> ISSN: 0254-5330

>

> 3. Management Science

> ISSN: 0025-1909

>

>

> If anyone have any useful reference about it, please let me know.

> Thank you for your attention.

> Best regards/chenyu

>

>

>

> --- In aima-talk@yahoogroups.com, seA <sea12_02@y...> wrote:

> > can i represent this VRP as a Reinforcement Learning problem?

> becaus im thinking about using RL for my mini project,any idea?

> >

> > regards,

> > seA/indonesia

> >

> > ³ÂÓí <chenyu468@y...> wrote:

> > Hi,

> > Yes, ¡®Vehicle route problem¡¯ is a search problem. It is a

central

> > problem in distribution management. The classical problem¡¯s

> > description is:

> > Fact:

> > 1. brief:

> > a) One company has many customers for distribution products.

> > The company has many vehicles fore doing the work. Every

customer¡¯

> s

> > order is small. Company wants to design a plan for all vehicles

to

> > lower the distribution cost.

> > 2. details:

> > a) G = (V,E) be an undirected graph where V = {v0,v1,?

> amp;shy;vn} is

> > a set of vertices representing customers. E ={(vi,vj)|vi,vj

belong

> to

> > V, i<j} is the edge set.

> > b) Vertex v0 denotes a depot at which are based m identical

> > vehicles of capacity Q, where m is a decision variable or a

> constant.

> > c) Each customer of V\{v} has a non-negative demand qi, a

non-

> > negative service time si. (waiting, unloading time)

> > d) A distance matrix (cij) is defined on E. We use the terms

> > distance and travel time interchangeably.

> > Problem(VRP---for vehicle route problem

> > 1. designing a set of m vehicles routes having a minimum

total

> > length and such that

> > a) each route start and ends at the depot

> > b) each remaining city is visited exactly once by one vehicle

> > c) the total demand of a route does not exceed

> > d) The total duration of a route does not exceed a preset

> > limit L.

> >

> > Many people think that the core of VRP is TSP (traveling salesman

> > problem). But it is more difficult than TSP. TSP has only one

> > salesman.

> >

> > Many variants of VRP exists,

> > 1. To delete the above fact b. Some customer¡¯s order is

very

> > big so that the order is more than the vehicle¡¯s capacity.

> > 2. Another special vertex appears. It is not customer. It is

> > highway fee collection point. Therefore the Problem-1 requirement

> > should be modified.

> > 3. Many different kind of vehicle exists, For example, one

> > kind of vehicles are for freezing products, one kind of vehicles

> are

> > for common products.

> > 4. Every vehicle can have more than 1 route.

> > 5. etc.

> >

> >

> >

> > There are many different approachs to solve the problem:

> > 1. hill climbing

> > 2. simulated annealing

> > 3. neural network

> > 4. GA

> > 5. ant system

> > 6. etc

> >

> > I think many knowledge of AIMA can be applied to this problem,

and

> > this problem¡¯s requirement is easy to imagine and new

requirement

> > can be added for more difficulty.

> >

> >

> >

> >

> > Thank you for your attention.

> > Best regards/chenyu (shanghai, China)

> >

> >

> >

> > Do you Yahoo!?

> > Yahoo! Mail - More reliable, more storage, less spam