Алгоритмы оценки стоимости маршрутов

[gbagretsov]

Использовать голландский аукцион для поднятия цены пассажиром - потихоньку поднимает цену, пока водитель не согласится.

Когда берём пассажира, разделяем маршрут на части:

• маршрут от нашего старта до старта пассажира
• от старта пассажира до финиша пассажира
• от финиша пассажира до нашего финиша

Если несколько пассажиров, рассмотреть все варианты перестановок маршрутов и выбрать оптимальный

[nshindarev]

Водитель рассчитывает номинальную стоимость маршрута + добавляет свою наценку (изменяемый коэффициент). Он просит разделить со своими пассажирами стоимость этого маршрута. Нужно учитывать то, что не все пассажиры проезжают полный маршрут.

Пассажир стучится к нескольким водителям со своим предложением. Параллельно пытается договориться со всеми. Он постепенно поднимает цену, либо пока какой-нибудь водитель не согласится, либо пока его собственная поездка не станет дешевле.

Если пассажир так и не найдёт водителя, а машины у него нет, то пишем, что он не смог договориться (для начала).

[nshindarev]

1) Научил пассажира определять подходит ли ему маршрут

[gbagretsov]

        if (car != null) {
            addBehaviour(new RegisterInYPBehaviour());
            addBehaviour(new HandlePassengersOffersBehaviour(this, 3000));

            this.wayWithMyCar = null;
            getWayByMyCar();
            getCostByMyCar();
        }

поменяй, пожалуйста, на

        if (car != null) {
            this.wayWithMyCar = null;
            getWayByMyCar();
            getCostByMyCar();

            addBehaviour(new RegisterInYPBehaviour());
            addBehaviour(new HandlePassengersOffersBehaviour(this, 3000));
        }

А то возможна такая ситуация, когда водитель при регистрации ещё не увидит свой начальный маршрут. Чисто теоретически. На практике такого не возникало, но лучше предусмотреть.

[nshindarev]

Логика поведения SearchDriversOffersBehaviour

[nshindarev]

Добавлены методы countAcceptablePrice(String start, String finish) и canTakePassenger(double cashValue, String start, String finish) внутри водительского поведения HandlePassengersOffersBehaviour: они высчитывают приемлимые цены для пассажира на основе того, придется ли водителю за ним "заезжать". Если предлагаемая пассажиром цена >= посчитанной цены проезда водителем, то возвращаем True, иначе False.

Также учитывается "коэфициент вредности водителя" - поле greed в классе CitizenAgent, который у каждого водителя свой добавляет от 0 до 15% от общей стоимости цены за бензин к минимальной приемлимой цене за проезд.

[gbagretsov]

Для водителя: Необходимо для каждого возможного множества из заявок пассажиров оценивать выгоду.

Формула: pp < (pd - cd) < p0, где pp - цена, которуб агент заплатит в качестве пассажира (постоянно повышается), pd - суммарный профит для водителя, который он получит, если возьмёт множество пассажиров, cd - суммарные траты водителя, которые он понесёт, если возьмёт множество пассажиров, (pd, cd вычисляются для каждого возможного подмножества пассажиров) p0 - изначальная стоимость поездки водителя (если он сам поедет; эта никода не меняется).

В момент, когда неравенство изменится (т.е. становится невыгодно быть пассажиром), говорим, что мы теперь 100% водитель.

В упрощённом случае: делаем всем водителям capacity = 1

[gbagretsov]

Ещё упоминался какой-то алгоритм (Флойда-Уоршелла, походу) для поиска кратчайших путей из каждой вершины в каждую. Один раз выполнили и сохранили таблицу, доступную всем водителям. Это чтобы не юзать каждый раз Дейкстру, потому что (цитата) "мы сдохнем".

[nshindarev]

Алгоритм реализован в поведении CheckPassengerPoolBehaviour в методе checkInequality