Author 
Message 
Richard Dobis science forum beginner
Joined: 26 Feb 2006
Posts: 9

Posted: Mon Feb 27, 2006 7:21 am Post subject:
LP  Shortest path with customer satisfaction



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
predefined 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

Posted: Mon Feb 27, 2006 11:09 pm Post subject:
Re: LP  Shortest path with customer satisfaction



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
predefined 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 



The time now is Thu Jan 17, 2019 6:25 am  All times are GMT

