FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
LP - Shortest path with customer satisfaction
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
Richard Dobis
science forum beginner


Joined: 26 Feb 2006
Posts: 9

PostPosted: Mon Feb 27, 2006 7:21 am    Post subject: LP - Shortest path with customer satisfaction Reply with quote

Hi all,

I have been working with the following problem. Example: Travel agency wants
to take people from city A to city B. Of course it want do it in such a way
that minimize total transportation costs. BUT it also looks for a customer
satisfaction. It want to choose the way that gives to customer at least
pre-defined level of satisfaction.

Model of the problem:
Graph with directed arcs. Cycles are there. It is not a tree. Each arc has
two numbers assigned - c_a: cost of traversing arcs a - p_a: pleasure that
recieve customer by traversing arc a. All numbers c_a and p_a are positive.
Let P by minimal allowed level of pleasure that is acceptable by cusomers.

The LP formulation of the above problem is:

Min Sum_a c_a arc_s
S.t.:
A arc = b ---- flow conservation constraints
sum_a p_a arc_a >= P
arc_a is binary {0,1}

Simple computing this by LP solver don't deliver a path. Sometimes it
deliver shortest path in the unconstrained sense (like withou pleasure
constraint) and several cycles that are not connected to the shortest path.

I need hint for solving this problem. How to transform above formulation to
the resource constrained shortest path problem? Any arcicles?

In the similar case where p_a is not pleasure but resource, time or risk the
model is as follows:

Min Sum_a c_a arc_s
S.t.:
A arc = b ---- flow conservation constraints
sum_a t_a arc_a <= T
arc_a is binary {0,1}

where t_a>=0 is time that consumes traversing arc a.

Interpretation is as follows: Travel agency look for cheapest path from city
A to city B that lasts at most T.

In this case simple LP solver deliver solution that is acceptable.


Thank you for any hint - advice, article, idea ....

richard
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Mon Feb 27, 2006 11:09 pm    Post subject: Re: LP - Shortest path with customer satisfaction Reply with quote

Richard Dobis wrote:
Quote:
Hi all,

I have been working with the following problem. Example: Travel agency wants
to take people from city A to city B. Of course it want do it in such a way
that minimize total transportation costs. BUT it also looks for a customer
satisfaction. It want to choose the way that gives to customer at least
pre-defined level of satisfaction.

Model of the problem:
Graph with directed arcs. Cycles are there. It is not a tree. Each arc has
two numbers assigned - c_a: cost of traversing arcs a - p_a: pleasure that
recieve customer by traversing arc a. All numbers c_a and p_a are positive.
Let P by minimal allowed level of pleasure that is acceptable by cusomers.

The LP formulation of the above problem is:

Min Sum_a c_a arc_s
S.t.:
A arc = b ---- flow conservation constraints
sum_a p_a arc_a >= P
arc_a is binary {0,1}

Simple computing this by LP solver don't deliver a path. Sometimes it
deliver shortest path in the unconstrained sense (like withou pleasure
constraint) and several cycles that are not connected to the shortest path.

c_a is 0 along any edge of any of these cycles, right?

You could get rid of the cycles by replacing c_a = 0 with c_a = (a
small positive number, depending on the data). This shouldn't affect
the minimum path much, and it will eliminate the cycles.

--- Christopher Heckman
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Tue Sep 19, 2017 5:17 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Advanced analytical methods for path integral calculation jaykov1 Particle 0 Tue Jul 11, 2006 2:36 am
No new posts Question about the path of a particle in Schwarzschild re... Oh No Research 5 Mon Jul 10, 2006 3:55 am
No new posts Advanced analytical methods for path integral calculation. jaykov1 num-analysis 0 Sat Jul 08, 2006 11:36 pm
No new posts Bezier track path with inversions DJ Wiza Math 0 Thu Jun 22, 2006 8:58 am
No new posts Shortest Non-Ionizing Wavelength? Radium Electromagnetics 6 Sat Jun 03, 2006 9:57 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0169s ][ Queries: 16 (0.0030s) ][ GZIP on - Debug on ]