2
$\begingroup$

Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - you find out immediately at the end of the conversation with that customer whether they agree or not. You have no control over the $t_i$ or $p_i$ values but you choose in which order to call the customers. So, once you've chosen the order, you just call the customers one by one, each immediately after the last one, until you make the sale (can ignore the case where you never make the sale, as having negligible probability).

You want to minimise the expected/average amount of time until you succeed in your sale (you only need one sale).

I would like to find an algorithm to find that optimal ordering of the customers.

Here is what I thought about so far:

  • Let $\sigma$ be a chosen order, i.e.a permutation of the $N$ indices. Let $I_{\sigma(i)}$ be an indicator random variable signifying that you speak to the $i$-th customer in your ordering $\sigma$.

    Then the random variable corresponding to the amount of time taken is $T(\sigma) = I_{\sigma(1)}t_{\sigma(1)} + I_{\sigma(2)}t_{\sigma(2)} + ... + I_{\sigma(N)}t_{\sigma(N)} $. Then, the average amount of time is $E(T(\sigma)) = E(I_{\sigma(1)}t_{\sigma(1)} + I_{\sigma(2)}t_{\sigma(2)} + ... + I_{\sigma(N)}t_{\sigma(N)}) = E(I_{\sigma(1)})t_{\sigma(1)} + E(I_{\sigma(2)})t_{\sigma(2)} + ... + E(I_{\sigma(N)})t_{\sigma(N)}$

    $E(I_{\sigma(i)})$ is the probability that you end up speaking with the $i$-th customer in the order, which is the probability that all preceding ones in the order fail, i.e. $E(I_{\sigma(N)}) = (1 - p_{\sigma(1)})(1 - p_{\sigma(2)})...(1 - p_{\sigma(i - 1)})$

    So overall the expected time is $t_{\sigma(1)} + (1 - p_{\sigma(1)})t_{\sigma(2)} + (1 - p_{\sigma(1)})(1 - p_{\sigma(2)})t_{\sigma(3)} + ...$

    So that at least gives the function we want to minimise.

  • I thought of using dynamic programming, but onyl thought of ways to do it where I store the optimal ordering for each subset, of the $2^N$ subsets. I also thought of a kind of bubble sort where I start with some order and then try to swap two adjacent customers and see if that gives a better result, but that seems to me a greedy algorithm and not sure if woudl give the overall optimal result.

$\endgroup$
3
  • $\begingroup$ I have a feeling that this question already appeared more than once on this site. $\endgroup$ Dec 3, 2021 at 10:34
  • $\begingroup$ I did look through the suggestions when writing the question, and also searched for "optimal order" but didn't find one like this one . $\endgroup$
    – AlexM
    Dec 3, 2021 at 12:14
  • $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W.
    Dec 3, 2021 at 20:53

1 Answer 1

0
$\begingroup$

We can assume that $p_i > 0$ for all $i$: if $p_i = 0$, ask them last.

Consider a certain arrangement, where customer $j$ is contacted directly after customer $i$. What happens if we switch the order of $i$ and $j$? For a certain $\rho \ge 0$, we replace $$ \rho t_i + \rho (1-p_i) t_j $$ with $$ \rho t_j + \rho (1-p_j) t_i $$ in the sum. The difference between these two options (former minus latter) is $$ \Delta = \rho (p_j t_i - p_i t_j) = \rho p_i p_j \left( \frac{t_i}{p_i} - \frac{t_j}{p_j} \right). $$ This suggests the following greedy rule:

Arrange the customers in nondecreasing order of $\displaystyle\frac{t_i}{p_i}$.

Remaining details left to you.

$\endgroup$
2
  • $\begingroup$ Thought about it in my head a bit, and it seems indeed to give the optimal order, would you agree? it seems to me that if there was a better order then it could be acquired by shifting some customers to be earlier in the order, but that would be equivalent to making multiple swaps of adjacent ones, each of which would give a negative difference in the way you've shown, so a total negative difference, contradicting the assumption that order was better than then one you gave. $\endgroup$
    – AlexM
    Dec 3, 2021 at 12:24
  • $\begingroup$ As I wrote, all remaining details are left to you. $\endgroup$ Dec 3, 2021 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.