Автоматика и телемеханика, № 5, 2020

Б.М. РОЗИН, канд. техн. наук (rozin@newman.bas-net.by),

Н.Н. ГУЩИНСКИЙ, канд. физ.-мат. наук (gyshin@newman.bas-net.by)

(Объединенный институт проблем информатики НАН Беларуси, Минск)

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ И АЛГОРИТМ СЛУЧАЙНОГО

ПОИСКА ДЛЯ ЗАДАЧИ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ

ЗАМЕНЫ ТРАДИЦИОННОГО ОБЩЕСТВЕННОГО

ТРАНСПОРТА ЭЛЕКТРИЧЕСКИМ¹

Исследуется сложная оптимизационная задача, возникающая при пла-

нировании процесса перехода от традиционного общественного транспор-

та к электрическому. Описываются предположения, входные и выходные

параметры задачи, а также ее математическая модель и рандомизирован-

ный алгоритм решения. Приводится библиография публикаций по иссле-

дуемой задаче.

Ключевые слова: электрический транспорт, оптимизация, математическое

программирование, рандомизированный алгоритм.

DOI: 10.31857/S0005231020050049

1. Введение

В статье исследуется оптимизационная задача, возникающая при плани-

ровании процесса замены парка традиционного общественного транспорта

электробусами для заданного множества маршрутов. Предполагается, что

электробус оборудован устройством хранения электрической энергии - ба-

тареей, которая требует периодической зарядки. В статье рассматривается

только технология зарядки, при которой батареи электробусов заряжаются

на стационарных станциях зарядки. Замена батарей и зарядка во время дви-

жения не предусматриваются.

Парк электробусов характеризуется типами электробусов и количеством

электробусов каждого типа. С каждым типом электробуса связаны следую-

щие характеристики такого же типа: множество подходящих типов станции

зарядки; время зарядки до рекомендуемого уровня состояния заряда (State

Of Charge (SOC)) при отправлении от станции зарядки одного и того же ти-

па, расположенной в одном и том же месте (депо или остановка); индикаторы

допустимого движения между любыми двумя остановками одного и того же

маршрута; потребление энергии для одного и того же маршрута в течение

года; годовые капитальные и эксплуатационные расходы; пассажировмести-

мость.

¹ Работа выполнена в рамках проекта PLATON инициативы ERA-NET Cofund Electric

Mobility Europe.

Маршрут характеризуется указанием депо и цикла маршрута, представ-

ляющего последовательность остановок, циклически посещаемых электро-

бусами этого маршрута. Интенсивностью пассажиропотока цикла маршру-

та является историческая или запланированная общая вместимость пасса-

жирских транспортных средств, отправляющихся с любой остановки этого

цикла в единицу времени. Блоком циклов маршрута будем называть после-

довательность следующих друг за другом циклов этого маршрута, модели-

руемых одной и той же интенсивностью пассажиропотока и одними и теми

же индикаторами допустимого движения. Для каждого маршрута будем рас-

сматривать обеспечивающий глобальную допустимость (ОГД) блок циклов,

такой что допустимое решение, принятое для этого блока циклов, является

допустимым для любого другого блока циклов в течение года. С некоторой

степенью неопределенности ОГД блок циклов может быть охарактеризован

максимальными потерями уровня SOC при движении по тем же сегментам

маршрута в сравнении с другими блоками циклов.

Для заданного маршрута частота отправления электробусов некоторого

типа равна количеству электробусов этого типа, отправляющихся с любой

одной и той же остановки этого маршрута в единицу времени. Задача опти-

мизации заключается в определении

• парка электробусов,

• частоты отправления электробусов каждого типа в ОГД блоке циклов для

каждого маршрута,

• мест установки станций зарядки и трансформаторов,

• количества станций зарядки каждого типа в каждом выбранном для них

месте,

• назначения мест установки станций зарядки трансформаторам и

• назначения станций зарядки маршрутам

таким образом, чтобы электробусам хватало заряда для движения по марш-

рутам и не была превышена выделенная (на зарядку электробусов) мощность

любого трансформатора. В качестве критерия рассматривается максимиза-

ция отношения общей эффективности (положительного экологического или

социально-экологического эффекта, выраженного количественно) к сумме об-

щих капиталовложений и эксплуатационных расходов (включая стоимость

потребляемой энергии), т.е. максимизация удельной эффективности инвести-

ций. В дальнейшем обозначим эту задачу через P. Предполагается, что реше-

ние задачи P будет повторяться для нескольких последовательных периодов

планирования. Элементы решения, принятые в предыдущий период, включа-

ются во входные данные для будущего периода. Такой подход последователь-

ной оптимизации основан на предположении, что оптимизация для ближай-

шего периода времени более эффективна, чем оптимизация для последующих

периодов, когда не все входные данные достаточно точно определены.

Задача P сложна как с точки зрения вычислений, так и с точки зрения

построения адекватной математической модели. Чтобы решить ее с прием-

лемым качеством за приемлемое время, в статье сделан ряд предположений,

которые приведены в разделе 3. Входные и выходные данные описаны в раз-

делах 4 и 5 соответственно. Математическая модель представлена в разде-

ле 6. В разделе 7 предложен рандомизированный эвристический алгоритм

для решения поставленной задачи. В разделе 2 приводится список публи-

каций, известных авторам настоящей статьи по рассматриваемой проблеме,

классифицированных по тематике.

2. Классификация публикаций по тематике

Подходящие публикации классифицируется по категориям, связанным

с планированием внедрения и эксплуатацией электрических транспортных

средств (EVs). Названия категорий приведены далее и сопровождаются спис-

ком соответствующих публикаций. Если публикация может быть отнесена к

нескольким категориям, то она расположена в той, которая, по мнению ав-

торов, является более подходящей.

• История и статистика использования EVs и соответствующей инфраструк-

туры: ZeEUS eBus Report [1], Nikolič иŽivanovič [2], Li [3], Ahmad и др. [4],

Anderson и др. [5], Todorovic и Simic [6].

• Анализ тестирования и эксплуатации EVs в реальных условиях: Barnitt [7],

Wang и González [8], Erkkilä и др. [9], Schmidt и др. [10], ZeEUS Demonstra-

tions [11], Foltinski [12], Rogge и др. [13], Hanlin [14], Olsson и др. [15], Eudy

и Jeffers [16], Gao и др. [17], Leou и Hung [18], Christensen и др. [19], Khan

и др. [20], Xylia и Silveira [21], Gallet и др. [22], Morganti и Browne [23].

• Сравнение EVs и транспортных средств с другими источниками энергии:

Feng и Figliozzi [24, 25], Hallmark и др. [26], Lajunen [27], Mohamed и др. [28].

• Имитационное моделирование эксплуатации EVs: Schoch [29], Teoh и др.

[30, 31], Mohamed и др. [32], Marmaras и др. [33], Xylia и др. [34], Fiori и

др. [35].

• Оптимизация эксплуатации EVs и требуемой инфраструктуры: Alonso и

др. [36], Wen и др. [37], Yu и др. [38], Juan и др. [39], Hiermann и др. [40],

Quak и др. [41], Desaulniers и др. [42], Wielinski и др. [43], Kunith и др. [44],

Bruglieri и др. [45], Pelletier и др. [46-49], Froger и др. [50, 51], Xylia и др. [52],

Liu и др. [53], Hosseini и Sarder [54], Wang и др. [55], Wang и др. [56].

• Экологические проблемы: доклад Всемирной организации здравоохране-

ния [57], Sydbom и др. [58], доклады института Health Effects Institute

[59, 60], Ali [61], Chan и др. [62], монография IARC [63], Mohner [64], Mc-

Clennan [65], Gaskins и др. [66], статьи специального выпуска журнала

Transportation Research Part D под редакцией Johem и др. [67].

Анализ приведенных публикаций показывает, что количество математиче-

ских моделей и алгоритмов решения задач оптимизации эксплуатации элек-

трического общественного транспорта и необходимой инфраструктуры недо-

статочно, чтобы охватить огромное число разнообразных реальных практи-

ческих ситуаций.

3. Предположения и допущения

В задаче P предполагается следующее:

1. Для каждого маршрута известны депо, промежуточные и конечные оста-

новки, а также порядок их посещения соответствующими электробусами;

Парк традиционных автобусов может замещаться частично;

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

маршрут назначен хотя бы один электробус, то по крайней мере одна под-

ходящая станция зарядки должна быть открыта в депо этого маршрута;

Маршруты могут пересекаться в депо, на конечных и промежуточных

остановках;

Любой электробус некоторого типа, назначенный на некоторый маршрут,

заряжается до рекомендуемого уровня SOC каждый раз, когда он посе-

щает место со станцией зарядки того типа, который назначен этому типу

электробусов и этому маршруту. Если указанное назначение не сделано

для подходящей четверки (тип электробуса, маршрут, место, тип станции

зарядки), то при моделировании электробус посещает указанное место без

зарядки;

В месте зарядки один и тот же тип станции зарядки может быть назна-

чен разным типам электробусов. В этом случае электробусы этих типов

совместно используют станции зарядки этого типа в этом месте;

Электробусы одного и того же типа и маршрута в одном и том же месте

заряжаются на станциях одного типа;

Каждая станция зарядки в одном и том же месте соединяется с одними

и теми же m трансформаторами. В каждый момент времени только одно

произвольное соединение места расположения станции зарядки с транс-

форматорами является активным;

Некоторые электробусы, станции зарядки и их связи с трансформаторами

к моменту принятия решения могут уже использоваться. В дальнейшем

будем их называть “старые”, а электробусы и элементы инфраструктуры,

относительно которых принимается решение, будем называть “новые”;

10.

Время, затрачиваемое любым электробусом на прохождение каждого из

ОГД блоков циклов, не меняется для одного и того же маршрута, и оно

определяется как некоторая оценка или достаточно точная верхняя гра-

ница этого времени.

4. Входные данные

Строчные буквы используются для обозначения числовых входных дан-

ных (параметров), а прописные - для обозначения множеств и переменных.

• Транспортная и электрическая сеть G = (NN, R, EE), которая представ-

ляет собой взвешенный смешанный мультиграф с множеством вершин

(мест для станций зарядки и трансформаторов) NN, множеством ориен-

тированных циклов (маршрутов) R и множеством ребер (связей с транс-

форматорами) EE, см. рисунок в качестве иллюстрации. На этом рисунке

маршрут 1 определяется циклом (Депо-1, 1, 2, 3, 4, 1, Депо-1), маршрут 2 -

(Депо-2, 5, 2, 3, 6, 5, Депо-2) и маршрут 3 - (Депо-3, 7, 8, 4, 3, 7, Депо-3).

• Множество NN разбито на множество T

“трансформаторных” вершин,

соответствующих приемлемым местам расположения трансформаторов, и

множество N

“нетрансформаторных” вершин.

Трансформатор-2

Депо-2

Депо-3

Депо-1

Трансформатор-1

Сеть для трех маршрутов.

•

Множество N разбито на подмножества ND и NE вершин депо и вершин

остановок соответственно, в которых могут быть установлены станции за-

рядки.

•

Множество N содержит подмножество NO нетрансформаторных вершин,

в каждой из которых открыта хотя бы одна старая станция зарядки любого

типа.

•

Множество T содержит подмножество T O трансформаторных вершин, в

каждой из которых находится по крайней мере один старый трансформа-

тор с ненулевой выделенной мощностью для новых электробусов.

•

Множество маршрутов R построено на основе множеств ND и NE. Одна

и та же вершина может принадлежать разным маршрутам.

•

Подмножество R₀ ⊆ R маршрутов, обслуживаемых хотя бы одним старым

электробусом.

•

Дуга (i, j) ∈ r, r ∈ R, представляет собой ориентированный участок марш-

рута, идущий из нетрансформаторной вершины i в нетрансформаторную

вершину j.

•

Ребро (i, j) ∈ EE представляет собой приемлемое соединение трансфор-

маторной вершины i и нетрансформаторной вершины j.

•

Множество B типов электробусов.

•

Подмножество BO, BO ⊆ B, старых типов электробусов.

•

Множество C типов станций зарядки.

Тип c ∈ C характеризуется следующими параметрами:

•

Номинальная мощность po_c одной станции зарядки;

•

Капитальные затраты cc^cap, включающие стоимость приобретения и уста-

новки одной станции зарядки без учета затрат, относящихся к подключе-

нию к трансформаторам;

•

Расходы cc^cpe на эксплуатацию одной станции зарядки в течение года;

•

Множество N_c ⊆ N вершин, приемлемых для открытия станции зарядки

типа c;

•

Множество NO_c ⊆NO вершин, в каждой из которых открыта хотя бы одна

старая станция зарядки типа c;

• Множество B_c ⊆ B типов электробусов, подходящих для станции зарядки

типа c.

Каждый тип электробуса b ∈ B характеризуется следующими параметра-

ми:

• Множество C_b подходящих типов станций зарядки. Электробус типа b мо-

жет заряжаться только на станциях типа c ∈ C_b;

• Множество NM_b нетрансформаторных вершин, в каждой из которых

должна быть открыта хотя бы одна станция зарядки типа c ∈ C_b, если

вершина принадлежит маршруту, обслуживаемому электробусами типа b;

• Множество R_b допустимых маршрутов, R_b ⊆ R;

• Пассажировместимость cap_b одного электробуса;

• Капитальные затраты cv^capb на один электробус;

• Расходы cv^opeb на эксплуатацию одного электробуса в течение года, не

включая стоимость потребляемой энергии;

Каждая нетрансформаторная вершина j ∈ N характеризуется следующи-

ми параметрами:

• Множество C_jb подходящих типов станций зарядки электробусов типа b.

Электробус типа b в вершине j может заряжаться только на станции типа

c∈C_jb;

• Число m соединений любой вершины j ∈ N\NO, в которой будет открыта

хотя бы одна новая станция зарядки, с трансформаторными вершинами.

Предполагается, что m ≤ |T |;

• Множество маршрутов R_j, пересекающихся в j;

• Множество TE_j ⊆ T трансформаторных вершин, допустимых для соеди-

нения с вершиной j;

• Количество nc_jc старых станций зарядки типа c, которые открыты в

j ∈ N_c, c ∈ C. Напомним, что если j ∈ NM_b и j принадлежит маршруту,

обслуживаемому старым электробусом типа b, то nc_jc ≥ 1 для c ∈ C_b;

• Множество RO_jcb маршрутов r таких, что их старые электробусы типа b

заряжаются на станциях типа c в вершине j, RO_jcb⊆R_j, j ∈ N_c, b ∈ R_b ∩B_c,

c∈C;

• Верхняя граница uc_jc на количество станций зарядки типа c, которые мо-

гут быть открыты в j ∈ N_c, c ∈ C. Этот параметр может быть опущен или

равен бесконечности, если отсутствует необходимость в его использовании;

• Верхняя оценка ct_jbc времени зарядки одного электробуса типа b на стан-

ции типа c ∈ C_b, открытой в j ∈ N_c, до рекомендованного уровня SOC,

либо оценка этого времени, которое для промежуточной остановки опре-

деляется средним временем посадки/высадки пассажиров, для конечной

остановки - максимальным временем замены или отдыха водителя, для

депо - продолжительностью пребывания в депо;

• Длительность t^depotj интервала времени I_j, в котором количество всех элек-

тробусов, находящихся в депо j ∈ ND, в единицу времени является наи-

большим.

Каждая трансформаторная вершина i ∈ T \T O характеризуется:

• запасами мощности o_i для питания новых станций зарядки в ОГД блоке

циклов;

• капитальной стоимостью трансформатора cb_i (cb_i = 0 для i ∈ T O).

Каждое ребро (i, j) ∈ EE связано с:

• затратами cl_ij на соединение трансформаторной вершины i и нетрансфор-

маторной вершины j.

Маршрут r ∈ R характеризуется следующими параметрами:

• Множество B_r типов электробусов, допустимых для обслуживания марш-

рута r;

• Последовательность π_r = (j₀, j₁, . . . , j_r, j₀) вершин, где j₀ - вершина депо

и j₁,... ,j_r - вершины остановок, которые посещаются циклически в ука-

занном порядке в течение ОГД блока циклов. Будем использовать записи

j ∈ r и (i,j) ∈ r для обозначения того, что вершина j и дуга (i,j) принад-

лежат маршруту r соответственно;

• Индикатор допустимого движения ei_r(i,j)b: ei_r(i,j)b = 1, если электробус ти-

па b может доехать из вершины i в вершину j маршрута r в ОГД блоке

циклов при условии, что станция зарядки типа c ∈ C_b установлена в i,

иначе ei_r(i,j)b = 0, i ∈ r, i ∈ N_c, j ∈ r, b ∈ B_r. Для заданного типа электро-

буса этот индикатор вычисляется на основе рекомендуемого уровня SOC,

минимального уровня SOC и условий движения по сегменту (i, j);

• Частота fr_rb движения старых электробусов типа b на маршруте r в ОГД

блоке циклов, fr_rb = 0 тогда и только тогда, когда ни один старый элек-

тробус типа b не назначен на маршрут r, b ∈ B_r;

• Нижняя граница lfr_rb, lfr_rb > 0, частоты движения новых электробусов

типа b на маршруте r в ОГД блоке циклов, если маршрут r выбран для

конверсии, b ∈ B_r;

• Верхняя граница ufr_rb, lfr_rb ≤ ufr_rb, частоты движения новых электро-

бусов типа b на маршруте r в ОГД блоке циклов, если маршрут r выбран

для конверсии, b ∈ B_r. Этот параметр может быть опущен или равен бес-

конечности, если отсутствует необходимость в его использовании;

• Наибольшая доля α^depotrbj, 0 < α^depotrbj ≤ 1, всех электробусов типа b, b ∈ B_r,

прибывающих в депо j ∈ ND за интервал времени длительности t^depotj.

Если t^depotj и α^depotrbj сложно определить, то можно положить длительность

t^depotj равной длительности интервала времени между прибытием послед-

него электробуса в депо j вечером предыдущего дня и отправлением перво-

го электробуса из депо j утром следующего дня, а также положить α^depotrbj =

= 1;

• Количество nv_rb старых электробусов типа b, назначенных на маршрут r

в ОГД блоке циклов, b ∈ B_r;

• Верхняя граница uv_rb количества новых электробусов типа b, назначенных

на маршрут r в ОГД блоке циклов, b ∈ B_r. Этот параметр может быть

опущен или равен бесконечности, если отсутствует необходимость в его

использовании;

• Верхняя оценка d_r продолжительности одного цикла любого электробуса

в ОГД блоке циклов;

• Верхняя оценка dc_rb суммарного времени зарядки одного электробуса ти-

па b в одном цикле ОГД блока циклов, b ∈ B_r;

• Стоимость энергии (или ее оценка) ce_rb, потребляемой одним электробусом

типа b на маршруте r в течение года, b ∈ B_r;

• Коэффициент предпочтения (вес) w_r, w_r ≥ 0;

• Нижняя граница lc > 0 суммарной капитальной и операционной стоимо-

сти.

• Верхняя граница uc, uc > lc, суммарной капитальной и операционной стои-

мости.

• Интенсивность пассажиропотока pas_r в ОГД блоке циклов, которая под-

держивается традиционными автобусами, и, следовательно, может под-

держиваться новыми электробусами;

• Функция co_r(Z), аппроксимирующая суммарные вредные выбросы тради-

ционных автобусов, которые перевозят Z пассажиров на маршруте r в

единицу времени ОГД блока циклов;

• Функция fu_r(Z), аппроксимирующая суммарное потребление топлива

традиционных автобусов, которые перевозят Z пассажиров на маршру-

те r в единицу времени ОГД блока циклов.

Замечание. Пусть Z_r обозначает максимальное количество пассажи-

ров, отправляющихся в новых электробусах от любой конечной или проме-

жуточной остановки маршрута r в единицу времени ОГД блока циклов. Оче-

видно, что Z_r ≤ pas_r. Предполагается, что значение эффективности (частич-

ной) конверсии для маршрута r выражается функцией v_r(Z_r) и предлагаются

три подхода для вычисления v_r(Z_r): 1) v_r(Z_r) = w_rZ_r, 2) v_r(Z_r) = w_rco_r(Z_r)

и 3) v_r(Z_r) = w_rfu_r(Z_r).

5. Выходные данные

Решение X задачи P может быть представлено следующими переменными:

• Частота F R_rb(X) новых электробусов типа b на маршруте r в ОГД блоке

циклов, где F R_rb = 0 тогда и только тогда, когда ни один новый электробус

типа b не обслуживает маршрут r, r ∈ R_b, b ∈ B;

• Множество R_jcb(X) маршрутов r таких, что fr_rb+FR_rb(X) > 0 и их старые

и новые электробусы типа b заряжаются на станциях типа c в вершине j,

RO_jcb ⊆ R_jcb(X) ⊆ R_j, j ∈ N_c, b ∈ R_b ∩ B_c, c ∈ C;

• Множество S_c(X) вершин j ∈ N_c, в каждой из которых открыта по край-

ней мере одна новая станция зарядки типа c;

• Количество NC_jc(X) новых станций зарядки типа c ∈ C, которые должны

быть установлены в нетрансформаторной вершине j ∈ S_c(X), c ∈ C;

• Множество L_j(X) трансформаторных вершин i ∈ TE_j, которые должны

быть соединены с нетрансформаторной вершиной j, j ∈ N\NO.

Решение X может быть использовано для вычисления следующих значе-

ний:

• B_r(X) = {b ∈ B_r | FR_rb(X) > 0} - множество типов электробусов таких,

что хотя бы один новый электробус такого типа назначен на маршрут

r∈R;

• B(X) = ∪_r∈RB_r(X);

• R_b(X) = {r ∈ R_b | FR_rb(X) > 0} - множество маршрутов, каждый из ко-

торых обслуживается хотя бы одним новым электробусом типа b, b ∈ B;

• R(X) = ∪_b∈BR_b(X);

• C(X) - множество типов старых и новых станций зарядки;

• S(X) = ∪_c∈C(X)S_c(X) - множество вершин, в каждой из которых установ-

лена хотя бы одна новая станция зарядки любого типа;

• R_j(X) - множество маршрутов, пересекающихся в вершине j и обслужи-

ваемых по крайней мере одним старым или новым электробусом, j ∈ S(X);

• SR_rb(X) - множество дуг маршрута r ∈ R_b(X), в каждой вершине j ко-

торых установлена хотя бы одна старая или новая станция зарядки типа

c ∈ C_jb для обслуживания электробусов типа b ∈ B(X), назначенных на

этот маршрут;

• c_jrb(X) - единственный тип новой или старой станции зарядки в вершине j

новых и старых электробусов типа b, назначенных на маршрут r;

• B_jc(X) = {b | c_jrb(X) = False,b ∈ B,r ∈ R_b} - множество типов электро-

бусов всех маршрутов, пересекающихся в j, которые будут заряжаться на

новых и старых станциях типа c, j ∈ S(X), c ∈ C(X);∑

• Z_r(X) =b∈Br(X) ^capb^FRrb(X) - интенсивность пассажиропотока марш-

рута r, поддерживаемая новыми электробусами (максимальное количество

пассажиров, отправляющихся в новых электробусах с любой остановки

маршрута r в единицу времени в ОГД блоке циклов), r ∈ R(X);

• NV_rb(X) = ⌈d_rFR_rb(X)⌉ - количество новых электробусов типа b, назна-

ченных на маршрут r в ОГД блоке циклов;∑

• FN_jb(X) =r∈Rj(X)^(frrb + FRrb(X)) - суммарная частота прибытия но-

вых и старых электробусов типа b в вершину j в ОГД блоке циклов, j ∈

∈ NE ∩ (S(X) ∪ NO), b ∈ B(X);

∑

- суммарная частота

• FN_jb(X) =r∈Rj(X) αrbjot(nvrb + NVrb(X))/t^jepot

прибытия новых и старых электробусов типа b ∈ B(X) в депо j, j ∈

∈ ND ∩ S(X), b ∈ B(X) за интервал времени I_j длительности t^depotj;

• M_i(X) = {j ∈ S(X) | i ∈ L_j(X)} - множество новых нетрансформаторных

вершин, связанных с трансформаторной вершиной i;

• T(X) - множество трансформаторных вершин, каждая из которых связа-

на с по крайней мере одной новой станцией зарядки;∑∑

• TP_i(X) =j∈Mi(X)∩N c∈C(X) ^poc^NCjc(X) - суммарная мощность новых

станций зарядки, соединенных с трансформаторной вершиной i ∈ T (X), в

ОГД блоке циклов;∑

• TP(X) =i∈T(X) TP_i(X) - суммарная мощность всех новых станций за-

рядки в ОГД блоке циклов;∑

• V (X) =r∈R(X) v_r(Z_r(X)) - общая эффективность;

∑

• CC(X) =_{c∈C(X)j∈S}

cc^cap

NC_jc(X) +_{r∈R(X)b∈B}

cv^capbNV_rb(X)+

(X)

r (X)

∑

cl_ij +_i∈T(X)\TO cb_i - капитальные затраты;

+ j∈S(X)\NO i∈L_j(X)

∑

• OC(X) =c∈C(X)j∈Sc

cccpe

(X)

NC_jc(X) +r∈R(X)b∈Br(X)(cvbpe+

+ ce_rb)NV_rb(X) - операционные затраты, включая стоимость электро-

энергии.

6. Постановка задачи

Обозначим через X область допустимых решений X задачи P. Она опре-

деляется системой соотношений:

(1)

lc ≤ CC(X) + OC(X) ≤ uc,

∑

(2)

Z_r(X) =

cap_bF R_rb(X) ≤ pas_r

r ∈ R(X),

b∈Br (X)

∑

(3)

TP_i(X) =

po_cNC_jc(X) ≤ o_i

i ∈ T(X),

j∈M_i(X) c∈C(X)

{

∑

}

′

pas_r -_b′_∈B(X),b′_=b capb′ lfrrb

lfr_rb ≤ FR_rb(X) ≤ min ufr_rb,

(4)

cap_b

r ∈ R_b(X), b ∈ B(X),

(5)

c_jrb(X) ∈ C_jb, j ∈ SR_rb(X), r ∈ R_b

(X), b ∈ B(X),

(6)

ei_r(i,j)b = 1, (i, j) ∈ SR_rb(X), r ∈ R_b

(X), b ∈ B(X),

∑

(7)

ct_jbc∗ ≤ dc_rb, c^∗ = c_jrb(X), r ∈ R_b

(X), b ∈ B(X),

j∈SR_rb(X)\ND

(8)

nv_rb + NV_rb(X) = nv_rb + ⌈d_rFR_rb(X)⌉ ≤ uv_rb, r ∈ R_b

(X), b ∈ B(X),

(9)

nc_jc + NC_jc(X) ≤ uc_jc, j ∈ S_c

(X), c ∈ C(X),

∑

(10)

(nc_jc + NC_jc(X)) ≥ 1, j ∈ NM_b

∩ S(X), b ∈ B(X) ∪ BO,

c∈C_b

∑

(11)

nc_jc + NC_jc(X) ≥

ct_jbcF N_jb

(X), j ∈ S(X) ∪ NO, c ∈ C,

b∈B_jc(X)

(12)

|L_j

(X)| = m, j ∈ S(X)\NO.

Соотношения (1) ограничивают суммарные капитальные и операционные за-

траты снизу и сверху. Соотношения (2) ограничивают сверху пассажиропоток

для каждого маршрута, обслуживаемого новыми электробусами. Ограниче-

ния (3) гарантируют, что общая мощность новых станций зарядки, соединен-

ных с одним и тем же трансформатором, не превышает выделенной мощности

этого трансформатора. Ограничения (4) определяют нижние и верхние гра-

ницы частоты движения новых электробусов. Ограничения (5) гарантируют,

что подходящая станция зарядки установлена в каждой вершине дуг мно-

жества SR_rb(X). При выполнении ограничений (6) любой новый электробус

может допустимо двигаться по своему маршруту, если подходящие станции

зарядки установлены в вершинах дуг множества SR_rb(X). Ограничения (7)

гарантируют, что общее время зарядки любого нового электробуса некото-

рого типа на некотором маршруте в одном цикле не превосходит верхнюю

границу для этого типа и маршрута. Ограничения (8) обеспечивают то, что

общее количество старых и новых электробусов каждого типа, обслуживаю-

щих один и тот же маршрут, не превосходит верхней границы, установлен-

ной для этого типа электробуса и маршрута. Соотношения (9) ограничивают

сверху общее количество новых и старых станций зарядки определенного ти-

па для каждой вершины. Ограничения (10) указывают, что по крайней мере

одна новая или старая станция зарядки типа c ∈ C_b должна быть установ-

лена в вершине множества NM_b, если эта вершина принадлежит маршруту,

обслуживаемому по крайней мере одним новым электробусом. Депо являет-

ся одной из таких вершин. Ограничения (11) гарантируют, что количества

новых и старых станций зарядки типа c, установленных в вершине j для об-

служивания электробусов типа B_jc(X) (всех маршрутов), достаточно для за-

рядки равномерно прибывающих электробусов без простоя в предположении,

что электробусы прибывают равномерно. Отметим, что равномерное прибы-

тие электробусов является упрощением реальной ситуации. При выполнении

ограничений (12) количество новых связей нетрансформаторной вершины,

в которой установлена хотя бы одна новая станция зарядки и нет старых

станций зарядки, с трансформаторными вершинами равно m.

Задача P формулируется так:

V (X)

max

X∈X CC(X) + OC(X)

Следует отметить, что оптимальное решение задачи P является Парето-

оптимальным решением трехкритериальной задачи максимизации V (X) и

минимизации CC(X) и OC(X) для X ∈ X , см. терминологию и результаты

по решению многокритериальных задач в Steuer [68], Vincke [69], Roy [70],

Collette и Siarry [71] и Ehrgott [72]. Поскольку задача P является сложной с

вычислительной точки зрения, в разделе 7 предлагается рандомизированный

эвристический алгоритм ее решения.

7. Рандомизированный эвристический алгоритм

Из-за вычислительной сложности задачи P предлагается следующий под-

ход к ее решению. Путем случайного выбора частей допустимых или недопу-

стимых решений строится множество допустимых решений Q ∈ X , которое,

как ожидается, будет содержать решения, близкие к оптимальному. Затем из

построенных решений выбирается наилучшее.

Формальное описание алгоритма, называемого далее алгоритмом A, при-

водится далее. Предполагается, что шаги алгоритма A выполняются по-

следовательно, если не указано другое. Алгоритм A использует вероятно-

сти для выбора определенного значения численной характеристики решения.

Эти вероятности являются управляющими параметрами алгоритма. Они мо-

гут быть определены лицом, принимающим решение, или установлены оди-

наковыми для всех возможных значений одной и той же характеристики

решения. В последнем случае предполагается равномерное распределение

вероятностей или распределение, настраиваемое по результатам численных

экспериментов.

Алгоритм A.

Шаг 1 (инициализация). Положить Q = ∅. На шагах 2-6 формируется

частичное решение Q. Оно может быть достроено до допустимого или недо-

пустимого полного решения.

Шаг 2 (формирование множества маршрутов R(Q), обслуживаемых по

крайней мере одним электробусом). Определить вероятности p_r, 0 ≤ p_r ≤ 1,

включения r ∈ R в R(Q). Положить p_r = 1 для старых маршрутов r ∈ R₀.

Сформировать множество R(Q), |R(Q)| ≥ 1, с помощью этих вероятностей.

Определить множество вершин N(Q) = {j | j ∈ R(Q)}.

Шаг 3 (формирование множества B_r(Q) типов электробусов для обслу-

живания маршрута r ∈ R(Q)). Для каждого маршрута r ∈ R(Q) определить

вероятность p_rb использования электробусов типа b на маршруте r, b ∈ B_r.

Положить p_rb = 1, если электробусы типа b уже используются на маршру-

те r. Сформировать множества B_r(Q), r ∈ R(Q), используя эти вероятности

таким образом, чтобы |B_r(Q)| ≥ 1 для всех r ∈ R(Q). Сформировать множе-

ство типов электробусов B(Q) = ∪_r∈R(Q)B_r(Q) и множества R_b(Q) маршру-

тов, обслуживаемых по крайней мере одним электробусом типа b ∈ B(Q).

Шаг 4 (формирование мест для станций зарядки и определение типов

c_jrb(Q) станций зарядки в вершине j для старых и новых электробусов ти-

па b, назначенных на маршрут r). Для каждого типа электробусов b ∈ B(Q) и

каждого маршрута r ∈ R_b(Q) сформировать множество дуг SR_rb(Q), в каж-

дой вершине j которых хотя бы одна старая или новая станция зарядки типа

c ∈ C_jb назначена типу электробусов b и маршруту r. Для заданных r и b

процесс формирования SR_rb(Q) начинается с включения в S_rb(Q) дуг, соеди-

няющих “обязательные” вершины множества NM_b ∩ r и вершины со стары-

ми станциями зарядки c ∈ C_b, назначенными b и r. Предполагается, что ти-

пы c_jrb(Q) станций зарядки заданы либо случайно сгенерированы для этих

обязательных вершин. Далее вычисляем текущее суммарное время зарядки∑

CT_rb(Q) =j∈SRrb(Q)\ND^ctjbc^∗,гдеc∗ =cjrb^{(Q).ЕслиCT}rb^(Q)>dcrb^,тоQ

не может быть достроено до полного допустимого решения. В этом случае

если время позволяет, то выполнить шаг 2, иначе выполнить шаг 7. Если

CT_rb(Q) ≤ dc_rb, то выполнить следующие вычисления. Рассмотрим произ-

вольную дугу (i₁, i₂) ∈ SR_rb(Q). Если eir(i1,i₂)b = 1, то дополнительная стан-

ция зарядки для электробусов типа b на маршруте r между вершинами i₁

и i₂ не нужна. Если eir(i1,i₂)b = 0, то включить в SRrb(Q) дуги (i1,j) и (j,i2),

j ∈ N_c ∩ r, c ∈ C_jb, такие что CT_rb(Q) + minc∈Cb{ct_jbc} ≤ dc_rb и eir(i1,j)b = 1

или eir(j,i2)b = 1 с некоторой вероятностью, которая может быть больше, ес-

ли расстояние от i₁ до j (соответственно от j до i₂) больше. Для допустимости

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

ной вершине j между i₁ и i₂ на этой итерации для пары (r, b). Если никакая

вершина не может быть включена и время позволяет, то выполнить шаг 2,

иначе выполнить шаг 7. Если дуги (i₁, j) и (j, i₂) включены в SR_rb(Q), то

определить тип станции зарядки c^∗ = c_jrb(Q) ∈ C_b для вершины j с некото-

рой вероятностью так, чтобы CT_rb(Q) + ct_jbc∗ ≤ dc_rb. Изменить текущее об-

щее время зарядки CT_rb(Q) := CT_rb(Q) + ct_jbc∗ . Повторять приведенный про-

цесс включения дуг до тех пор, пока не будет выполнено eir(i1,i₂)b = 1 для

любой дуги (i₁, i₂) ∈ SR_rb(Q). Сформировать множества S(Q), S_c(Q), C(Q) и

B_jc(Q), которые являются аналогами таких же множеств, определенных для

решения X. Отметим, что в конце этого шага будут выполнены соотношения

c_jrb(Q) ∈ C_jb, j ∈ SR_rb(Q), r ∈ R_b(Q), b ∈ B(Q),

ei_r(i,j)b = 1, (i, j) ∈ SR_rb(Q), r ∈ R_b(Q), b ∈ B(Q),

∑

ct_jbc∗ ≤ dc_rb, c^∗ = c_jrb(Q), r ∈ R_b(Q), b ∈ B(Q),

j∈SR_rb(Q)\ND

∑

(nc_jc + NC_jc(Q)) ≥ 1, j ∈ NM_b ∩ S(Q), b ∈ B(Q) ∪ BO,

c∈C_b

которые являются аналогами ограничений (5), (6), (7) и (10). Также отметим,

что NC_jc(Q) в последнем соотношении не определено явно, но это соотноше-

ние выполняется по определению шага 4.

Шаг 5 (формирование количеств NC_jc(Q) новых станций зарядки и ча-

стот отправления F R_rb(Q) новых электробусов). Определить NC_jc(Q)

FR_rb(Q) как решение задачи

V (F R(Q))

max

(NC(Q),F R(Q))∈N F(Q) CC(NC(Q), F R(Q)) + OC(NC(Q), F R(Q))

где

∑

V (F R(Q)) =

v_r(Z_r(Q)),

r∈R(Q)

∑

CC(NC(Q),FR(Q)) =

cc^capcNC_jc(Q) +

c∈C(Q) j∈Sc(Q)

∑

cv^capbNV_rb(Q),

r∈R(Q) b∈Br (Q)

∑

OC(NC(Q),FR(Q)) =

cc^opecNC_jc(Q) +

c∈C(Q) j∈Sc(Q)

∑

(cv^opeb + ce_rb)NV_rb(Q),

r∈R(Q) b∈Br (Q)

∑

Z_r(Q) =

cap_bF R_rb(Q),

b∈Br (Q)

NV_rb(Q) = ⌈d_rFR_rb(Q)⌉,

∑

FN_jb(Q) =

(fr_rb + F R_rb(Q)), j ∈ NE,

r∈R_j ∩R_b(Q)

∑

FN_jb(Q) =

α^depotrbj(nv_rb + NV_rb(Q))/t^depotj, j ∈ ND,

r∈R_j ∩R_b(Q)

и допустимая область N F(Q) определяется ограничениями:

(13)

lc ≤ CC(Q) + OC(Q) ≤ uc,

(14)

Z_r(Q) ≤ pas_r

r ∈ R(Q),

∑

(15)

TP_i(Q) =

po_cNC_jc(Q) ≤ o_i

i ∈ T(Q),

j∈M_i(Q)∩N c∈C(Q)

{

∑

}

′

pas_r -_b′_∈B(Q),b′_=b capb′ lfrrb

lfr_rb ≤ FR_rb(Q) ≤ min ufr_rb,

(16)

cap_b

r ∈ R_b(Q), b ∈ B(Q),

(17)

nv_rb + NV_rb(Q) = nv_rb + ⌈d_rFR_rb(Q)⌉ ≤ uv_rb, r ∈ R_b

(Q), b ∈ B(Q),





∑

(18)

nc_jc +NC_jc(Q) =

ct_jbcF N_jb(Q)

j ∈S(Q)∪NO, c∈C(Q),



b∈Bjc(Q)

∈ Z₊, NC_jc(Q) ∈ Z₊, j ∈ S(Q) ∪ NO,

(19)

FR_rb(Q)

r ∈ R(Q), b ∈ B_r(Q), c ∈ C(Q).

Для решения приведенной задачи используется метод роя частиц (Particle

Swarm Optimization), см. Clerc [73], Kennedy и Eberhart [74] и Pedersen и Chip-

perfield [75]. Если решение системы (13)-(19) найдено, то выполнить шаг 6.

Если решение не найдено и время позволяет, то выполнить шаг 2, иначе вы-

полнить шаг 7.

Шаг 6 (выбор новых связей станций зарядки и трансформаторов). Для

каждой вершины j ∈ S(Q)\NO обозначим через L_j (Q) множество трансфор-

маторных вершин, связанных с вершиной j в соответствии с частичным реше-

нием Q. Обозначим через M_i(Q) = {j ∈ S(Q) | i ∈ L_j (Q)} множество новых

нетрансформаторных вершин, связанных с трансформаторной вершиной i.

Множества L_j(Q), j ∈ S(Q)\NO, множества M_i(Q), i ∈ T , и множество T (Q)

новых трансформаторов отыскиваются случайно. Для каждой вершины

j ∈ S(Q)\NO определяется вероятность p_ij связи трансформаторной верши-

ны i ∈ T E_j с вершиной j. Эта вероятность может быть выше для большей

выделенной мощности o_i и она может быть выше для меньшей стоимости

cl_ij + cb_iy_i, где y_i = 1, если i ∈ T O, и y_i = 0, если i ∈ T O. Далее связать вер-

шину j ∈ S(Q)\NO с m вершинами i ∈ T . Вычислить капитальные затраты∑∑

∑

CC(Q) =j∈S(Q)\NOi∈Lj

cl_ij +_i∈T(Q)\TO cb_i + CC (NC(Q), F R(Q)).

(Q)

Установить Q := Q ∪ {Q}. Если время позволяет, то выполнить шаг 2, иначе

выполнить шаг 7.

Шаг 7. Найти Q^∗ ∈ Q такое, что

V (Q^∗)

V (Q)

= max

CC(Q^∗) + OC(Q^∗)

Q∈Q CC(Q) + OC(Q)

В рассматриваемых в настоящее время реальных ситуациях мощности

множеств, генерируемых на шагах 1-4, ограничены следующими значениями.

Количество маршрутов: |R| ≤ 18. Количество депо: |ND| ≤ 3. Количество ти-

пов станций зарядки: |C| ≤ 2. Количество маршрутов, пересекающихся в од-

ном месте, подходящем для установки станций зарядки: |R_j | ≤ 8 для j ∈ ND,

|R_j| ≤ 5 для j ∈ NE. Количество остановок одного маршрута, подходящих

для открытия станций зарядки: |N ∩ r| ≤ 5, r ∈ R. Количество типов элек-

тробусов, подходящих для обслуживания одного маршрута: |B_r| ≤ 5, r ∈ R.

Количество мест, в которых должна быть открыта хотя бы одна станция за-

рядки для электробусов одного типа и маршрута: 1 ≤ |NM_b ∩ r| ≤ 3, b ∈ B,

r ∈ R. Количество соединений с трансформаторами: m ∈ {1,2}. Количество

мест размещения трансформаторов, подходящих для соединения с одним и

тем же местом размещения станций зарядки: |T E_j | ≤ 2, j ∈ N.

8. Заключение

Исследована сложная оптимизационная задача, возникающая при плани-

ровании процесса перехода от традиционного общественного транспорта к

электрическому. Описаны принятые предположения, входные и выходные па-

раметры задачи, а также ее математическая модель и рандомизированный

алгоритм решения. Дальнейшая работа будет сконцентрирована на разра-

ботке детального алгоритма, его программной реализации и тестировании на

реальных примерах участников проекта PLATON.

Авторы выражают благодарность ведущему начному сотруднику ОИПИ

НАН Беларуси Я.М. Шафранскому за обсуждение постановки задачи и по-

лезные советы по ее моделированию.

СПИСОК ЛИТЕРАТУРЫ

1. http://zeeus.eu/uploads/publications/documents/zeeus-report2017-2018-final.pdf

2. Nikolič Z.,

Živanovič Z. The Contribution and Prospects of the Technical Develop-

ment on Iimplementation of Electric and Hybrid Vehicles // New Generat. Electric

Vehicles. 2012. Chapter 2. P. 27-66.

3. Li J.-Q. Battery-Electric Transit Bus Developments and Operations: A Review //

Int. J. Sustain. Transp. Technol. 2016. V. 10. P. 157-169.

4. Ahmad A., Khan Z.A., Alam M.S., Khateeb S. A Review of the Electric Vehicle

Charging Techniques, Standards, Progression and Evolution of EV Technologies in

Germany // Smart Sci. 2018. V. 6. No. 1. P. 36-53.

5. Anderson J.E., Lehne M., Hardinghaus M. What Electric Vehicle Users Wwant: Real-

World Preferences for Public Charging Infrastructure // Int. J. Sustain. Transp. 2018.

V. 12. No. 5. P. 341-352.

6. Todorovic M., Simic M. Current State of the Transition to Electrical Vehicles //

Smart Innovat. Syst. Technol. 2019. V. 98. P. 130-139.

7. Barnitt R. Case Study: Ebus Hybrid Electric Buses and Trolleys // National Re-

newable Energy Laboratory. Technical Report NREL/TP-540-38749. 2006.

8. Wang X., González J.A. Assessing Feasibility of Electric Buses in Small and Medium-

Sized Communities // Int. J. Sustain. Transp. 2013. V. 7. P. 431-448.

Erkkilä K., Nylund N.-O., Pellikka A.-P., Kallio M., Kallonen S., Ojamo S., Ruot-

salainen S., Pietikäinen O., Lajunen A. eBUS - Electric Bus Test Platform in Fin-

land // EVS27 International Battery, Hybrid and Fuel Cell Electric Vehicle Sympos.

Barcelona, Spain, 2013.

10.

Schmidt J., Eisel M., Kolb L.M. Assessing the Potential of Different Charging Strate-

gies for Electric Vehicle Fleets in Closed Transport Systems // Energ. Policy. 2014.

V. 74. P. 179-189.

11.

http://zeeus.eu/uploads/publications/documents/zeeus-local-demo-brochures-

mergedcompressed.pdf

12.

Foltynski M. Electric Fleets in Urban Logistics // Procedia - Social and Behavioral

Sciences. 2014. V. 151. P. 48-59.

13.

Rogge M., Wollny S., Sauer D.U. Fast Charging Battery Buses for the Electrification

of Urban Public Transport - a Feasibility Study Focusing on Charging Infrastructure

and Energy Storage Requirements // Energies. 2015. V. 8. No. 5. P. 4587-4606.

14.

Hanlin J. Battery Electric Buses Smart Deployment // Zero Emission Bus conf.

London, 2016.

15.

Olsson O., Grauers A., Pettersson S. Method to Analyze Cost Effectiveness of Dif-

ferent Electric Bus Systems // EVS29 Int. Battery, Hybrid and Fuel Cell Electric

Vehicle Sympos. Montreal. 2016. P. 1-12.

16.

Eudy L., Jeffers M. Foothill Transit Battery Electric Bus Demonstration Re-

sults: Second Report // National Renewable Energy Laboratory. Technical Report

NREL/TP-5400-67698. 2017.

17.

Gao Z., Lin Z., LaClair T.J., Liu C., Li J.-M., Birky A.K., Ward J. Battery Ca-

pacity and Recharging Needs for Electric Buses in City Transit Service // Energy.

2017. V. 122. P. 588-600.

18.

Leou R.-C., Hung J.-J. Optimal Charging Schedule Planning and Economic Analysis

for Electric Bus Charging Stations // Energies. 2017. V. 10. No. 4. 483.

19.

Christensen L., Klauenberg J., Kveiborg O., Rudolph C. Suitability of Commer-

cial Transport for a Shift to Electric Mobility with Denmark and Germany as Use

Cases // Res. Transp. Econ. 2017. V. 64. P. 48-60.

20.

Khan W., Ahmad A., Ahmad F., Alam M.S. A Comprehensive Review of Fast Charg-

ing Infrastructure for Electric Vehicles // Smart Sci. 2018. V. 6. No. 3. P. 256-270.

21.

Xylia M., Silveira S. The Role of Charging Technologies in Upscaling the Use of

Electric Buses in Public Transport: Experiences from Demonstration Projects //

Transport Res. A - Pol. 2018. V. 118. P. 399-415.

22.

Gallet M., Massier T., Hamacher T. Estimation of the Energy Demand of Electric

Buses Based on Real-World Data for Large-Scale Public Transport Networks //

Appl. Energ. 2018. V. 230. P. 344-356.

23.

Morganti E., Browne M. Technical and Operational Obstacles to the Adoption of

Electric Vans in France and the UK: An Operator Perspective // Transport Policy.

2018. V. 63. P. 90-97.

24.

Feng W., Figliozzi M. Conventional vs Electric Commercial Vehicle Fleets: A Case

Study of Economic and Technological Factors Affecting the Competitiveness of Elec-

tric Commercial Vehicles in the USA // Procedia - Social and Behavioral Sciences.

2012. V. 39. P. 702-711.

25.

Feng W., Figliozzi M. An Economic and Technological Analysis of the Key Factors

Affecting the Competitiveness of Electric Commercial Vehicles: A Case Study from

the USA Market // Transport Res. C - Emer. 2013. V. 26. P. 135-145.

26.

Hallmark S.L., Wang B., Sperry R. Comparison of On-Road Emissions for Hybrid

and Regular Transit Buses // J. Air Waste Manage. 2013. V. 63. No. 10. P. 1212-

1220.

27.

Lajunen A. Energy Consumption and Cost-Benefit Analysis of Hybrid and Electric

City Buses // Transport Res. C - Emer. 2014. V. 38. P. 1-15.

28.

Mohamed M., Garnett R., Ferguson M.R., Kanaroglou P. Electric Buses: A Review

of Alternative Powertrains // Renew. Sust. Energ. Rev. 2016. V. 62. P. 673-684.

29.

Schoch J. Modeling of Battery Life Optimal Charging Strategies Based on Empirical

Mobility Data // IT - Information Technology. 2016. V. 58. No. 1. P. 22-28.

30.

Teoh T., Kunze O., Teo C.-C. Methodology to Evaluate the Operational Suitability

of Electromobility Systems for Urban Logistics Operations // Transportation Res.

Procedia. 2016. V. 12. P. 288-300.

31.

Teoh T., Kunze O., Teo C.-C. Scenario-Based Electric Bus Operation: A Case Study

of Putrajaya, Malaysia // Int. J. Transp. Sci. Technol. 2018. V. 7. No. 1. P. 10-25.

32.

Mohamed M., Farag H., El-Taweel N., Ferguson M. Simulation of Electric Buses on

a Full Transit Network: Operational Feasibility and Grid Impact Analysis // Electr.

Pow. Syst. Res. 2017. V. 142. P. 163-175.

33.

Marmaras C., Xydas E., Cipcigan E. Simulation of Electric Vehicle Driver Behaviour

in Road Transport and Electric Power Networks // Transport Res. C - Emer. 2017.

V. 80. P. 239-256.

34.

Xylia M., Leduc S., Patrizio P., Silveira S., Kraxner F. Developing a Dynamic Opti-

mization Model for Electric Bus Charging Infrastructure // Transport. Res. Procedia.

2017. V. 27. P. 776-783.

35.

Fiori C., Ahn K., Rakha H.A. Optimum Routing of Battery Electric Vehicles: In-

sights Using Empirical Data and Microsimulation // Transport Res. D - Tr. E. 2018.

V. 64. P. 262-272.

36.

Alonso M., Amaris H., Germain J.G., Galan J.M. Optimal Charging Scheduling

of Electric Vehicles in Smart Grids by Heuristic Algorithm // Energies. 2014. V. 7.

P. 2449-2475.

37.

Wen M., Laporte G., Madsen O.B.G., Norrelund A.V., Olsen A. Locating Replen-

ishment Stations for Electric Vehicles: Application to Danish Traffic Data // J. Oper.

Res. Soc. 2014. V. 65. No. 10. P. 1555-1561.

38.

Yu Z., Chen S., Tong L. An Intelligent Energy Management System for Large-Scale

Charging of Electric Vehicles // CSEE J. Power Energy. 2016. V. 2. No. 1. P. 47-53.

39.

Juan A.A., Mendez C.A., Faulin J., de Armas J., Grasman S.E. Electric Vehicles in

Logistics and Transportation: A Survey on Emerging Environmental, Strategic, and

Operational Challenges // Energies. 2016. V. 9. No. 2. 86.

40.

Hiermann G., Puchinger G., Ropke S., Hartl R.F. The Electric Fleet Size and Mix

Vehicle Routing Problem with Time Windows and Recharging Stations // Eur. J.

Oper. Res. 2016. V. 252. P. 995-1018.

41.

Quak H., Nesterova N., van Rooijen T. Possibilities and Barriers for Using Electric-

Powered Vehicles in City Logistics Practice // Transport. Res. Procedia. 2016. V. 12.

P. 157-169.

42.

Desaulniers G., Errico F., Irnich S., Schneider M. Exact Algorithms for Electric

Vehicle-Routing Problems with Time Windows // Oper Res. 2016. V. 64. No. 6.

P. 1388-1405.

43.

Wielinski G., Trépanier M., Morency C. Electric and Hybrid Car Use in a Free-

Floating Car Sharing System // Int. J. Sustain. Transp. 2017. V. 11. No.

P. 161-169.

44.

Kunith A., Mendelevitch R., Goehlich D. Electrification of a City Bus Network -

An Optimization Model for Cost-Effective Placing of Charging Infrastructure and

Battery Sizing of Fast-Charging Electric Bus Systems // Int. J. Sustain. Transp.

2017. V. 11. No. 10. P. 707-720.

45.

Bruglieri M., Mancini S., Pezzella F., Pisacane O., Suraci S. A Three-Phase

Matheuristic for the Time-Effective Electric Vehicle Routing Problem with Partial

Recharges // Electron. Notes Discrete Math. 2017. V. 58. P. 95-102.

46.

Pelletier S., Jabali O., Laporte G. Battery Electric Vehicles for Freight Distribution:

A Survey of Vehicle Technology, Market Penetration, Incentives and Practices //

CIRRELT, CIRRELT-2014-43. Montreal. 2014.

47.

Pelletier S., Jabali O., Laporte G. 50th Anniversary Invited Article. Goods Distri-

bution with Electric Vehicles: Review and Research Perspectives // Transport Sci.

2016. V. 50. No. 1. P. 3-22.

48.

Pelletier S., Jabali O., Laporte G. Charge Scheduling for Electric Freight Vehicle //

Transport Res. B - Meth. 2018. V. 115 P. 246-269.

49.

Pelletier S., Jabali O., Laporte G., Veneroni M. Battery Degradation and Behaviour

for Electric Vehicles: Review and Numerical Analyses of Several Models // Transport

Res. B - Meth. 2017. V. 103. P. 158-187.

50.

Froger A., Mendoza J., Jabali O., Laporte G. New Formulations for the Electric Ve-

hicle Routing Problem with Nonlinear Charging Functions // CIRRELT, CIRRELT-

2017-30. Montreal. 2017.

51.

Froger A., Mendoza J., Jabali O., Laporte G. A Matheuristic for the Eectric Vehicle

Routing Problem with Capacitated Charging Stations // CIRRELT, CIRRELT-

2017-31. Montreal. 2017.

52.

Xylia M., Leduc S., Patrizio P., Kraxner F., Silveira S. Locating Charging Infras-

tructure for Electric Buses in Stockholm // Transport Res. C - Emer. 2017. V. 78.

P. 183-200.

53.

Liu Z., Song Z., He Y. Planning of Fast-Charging Stations for a Battery Electric

Bus System under Energy Consumption Uncertainty // Transport Res. Rec. 2018.

https://doi.org/10.1177/0361198118772953

54.

Hosseini S., Sarder M.D. Development of a Bayesian Network Model for Optimal Site

Selection of Electric Vehicle Charging Station // Int. J. Elec. Power. 2019. V. 105.

P. 110-122.

55.

Wang Y., Bi J., Guan W., Zhao X. Optimising Route Choices for the Travelling

and Charging of Battery Electric Vehicles by Considering Multiple Objectives //

Transport Res. D - Tr E. 2018. V. 64. P. 246-261.

56.

Wang Y.-W., Lin C.-C., Lee T.-J. Electric Vehicle Tour Planning // Transport Res.

D - Tr E. 2018. V. 63. P. 121-136.

57.

World Health Organization. Quantification of the Health Effects of Exposure to Air

Pollution. Report of a WHO Working Group. Bilthoven, Netherlands, 2000.

58.

Sydbom A., Blomberg A., Parnia S., Stenfors N., Sandström T, Dahlén S.E. Health

Effects of Diesel Exhaust Emissions // Eur. Respir. J. 2001. V. 17. No. 4. P. 733-746.

59.

HEI Panel on the Health Effects of Traffic-Related Air Pollution. Traffic-Related Air

Pollution: A Critical Review of the Literature on Emissions, Exposure, and Health

Effects. HEI Special Report 17. Health Effects Institute, Boston, MA, 2010.

60.

HEI Diesel Epidemiology Panel. Executive Summary. Diesel Emissions and Lung

Cancer: An Evaluation of Recent Epidemiological Evidence for Quantitative Risk

Assessment. HEI Special Report 19. Health Effects Institute, Boston, MA, 2015.

61.

Ali R. Effect of Diesel Emissions on Human Health: A Review // Int. J. Appl. Engin.

Res. 2011. V. 6. No. 11. P. 1333-1342.

62.

Chan S., Miranda-Moreno L.F., Patterson Z. Analysis of GHG Emissions for

City Passenger Trains: Is Electricity an Obvious Option for Montreal Commuter

Trains? // J. Transport. Technol. 2013. V. 3. No. 2A. P. 17-29.

63.

IARC Working Group on the Evaluation of Carcinogenic Risk to Humans. Diesel

and Gasoline Engine Exhausts and Some Nitroarenes. IARC Monographs on the

Evaluation of Carcinogenic Risks to Humans, No. 105 // Int. Agency for Research

on Cancer. Lyon, France, 2014.

64.

Mohner M. The Hidden Impact of a Healthy-Worker Effect on the Results of the

Diesel Exhaust in Miners Study // Eur. J. Epidemiol. 2016. V. 31. No. 8. P. 803-804.

65.

McClellan R.O. Critique of Health Effects Institute Special Report 19, “Diesel Emis-

sions and Lung Cancer: An Evaluation of Recent Epidemiological Evidence for Quan-

titative Risk Assessment” // Report. Albuquerque, NM, 2016.

66.

Gaskins A.J., Hart J.E., Minguez-Alarcón L., Chavarro J.E., Laden F., Coull B.A.,

Ford J.B., Souter I., Hauser R. Residential Proximity to Major Roadways and Traffic

in Relation to Outcomes of in vitro Fertilization // Environ. Int. 2018. V. 115.

P. 239-246.

67.

Jochem P., Plötz P., Ng W.-S., Rothengatter W. The Contribution of Electric Ve-

hicles to Environmental Challenges in Transport // Transport Res. D - Tr E. 2018.

V. 64. P. 1-4.

68.

Steuer R. Multiple Criteria Optimization: Theory, Computation and Application.

N.Y.: John Wiley & Sons, 1985.

69.

Vincke P. Multicriteria Decision Aid. N.Y.: John Wiley & Sons, 1992.

70.

Roy B. Multicriteria Methodology for Decision Aiding / Nonconvex Optim. Appl.

V. 12. Dordrecht: Kluwer Acad. Publishers, 1996.

71.

Collette Y., Siarry P. Multiobjective Optimization: Principles and Case Studies.

Springer Science & Business Media, 2004.

72.

Ehrgott M. Multicriteria Optimization. Springer Verlag, 2005.

73.

Clerc M. Particle Swarm Optimization. John Wiley & Sons, 2010.

74.

Kennedy J., Eberhart R. Particle Swarm Optimization // Proc. IEEE Int. Conf. on

Neural Networks. IV. 1995. P. 1942-1948.

75.

Pedersen M.E.H., Chipperfield A.J. Simplifying Particle Swarm Optimization //

Appl. Soft Comput. 2010. V. 10. P. 618-628.

Статья представлена к публикации членом редколлегии А.А. Лазаревым.

Поступила в редакцию 09.07.2019

После доработки 19.10.2019

Принята к публикации 28.11.2019