Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
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
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
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 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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Mon Mar 18, 2019 5:25 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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