配送計画モデルは，我が国では最も普及しているロジスティクス・ツールである配送計画システムの基幹を成すモデルである． 本来ならば，配送だけでなく集荷にも使われるので運搬経路問題（vehicle routing problem）と よぶのが学術用語としては正しい使い方だが，「運搬」という言葉のイメージが悪いためか， 実務家および研究者の間でも「配送計画」とよばれることが多いので，ここでもそれにならうものとする．
一般に，古典的な配送計画モデルの基本形は以下の仮定をもつ．
配送計画の応用としては，小売店への配送計画，スクールバスの巡回路決定，郵便や新聞の配達，ゴミの収集，燃料の配送などがある． もちろん，これらの応用に適用する際には，上の基本条件に新たな条件を付加する必要がある．
ここで考えるのは，ほとんどの実際問題を解けるようにするために，以下の一般化をした配送計画モデルである．
地点は顧客，積み込み積み下ろし地点，運搬車の発着地を順に並べたものである．最適化に使うのは経度・緯度の情報を保持したlocation列だけである． 移動時間の計算に地図を使用する場合には，以下のデータフレームで保持しているので必要はない．
移動時間を地図で計算しない場合には，この地点の番号を参照し，移動時間を計算したデータ（移動時間データ）を参照する．
例題においては，地点データの番号は以下の順に保管されている．
したがって，地点の数は，「ジョブ数 \(+\) 輸送数 \(\times 2 +\) デポ数」となる．
| name | zip | 都道府県 | 市区町村 | 大字 | location | |
|---|---|---|---|---|---|---|
| 4 | 合同会社山田水産 | 2820021 | 千葉県 | 成田市 | 駒井野（成田国際空港内） | [140.36806495,35.77641112] |
| 5 | 有限会社吉田食品 | 2992416 | 千葉県 | 南房総市 | 富浦町青木 | [139.8874225,35.06991256] |
| 6 | 有限会社青山鉱業 | 2700001 | 千葉県 | 松戸市 | 幸田 | [139.92525888,35.84571653] |
| 7 | 有限会社喜嶋建設 | 2720134 | 千葉県 | 市川市 | 入船 | [139.92142527,35.67868735] |
| 8 | 有限会社工藤水産 | 2830048 | 千葉県 | 東金市 | 幸田 | [140.38179168,35.53855767] |
ジョブは，荷物の集荷もしくは配達を希望している地点の総称であり，以下の列から構成される．
| name | service | pickup | delivery | time_windows | location | location_index | skills | priority | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 合同会社藤本建設 | 1068 | [56] | [244] | [[10820, 12620], [33575, 35375]] | [140.37645821,35.73859296] | 0 | [0,1] | 9 |
| 1 | 有限会社西之園運輸 | 852 | [75] | [229] | [[8151, 9951], [21049, 22849]] | [140.26801893,35.69354415] | 1 | [0,1] | 9 |
| 2 | 株式会社村山印刷 | 1090 | [100] | [683] | [[753, 2553], [27719, 29519]] | [140.07757664,35.654959999999996] | 2 | [0] | 7 |
| 3 | 青田印刷合同会社 | 998 | [70] | [849] | [[11742, 13542], [19888, 21688]] | [139.85405777,35.14919189] | 3 | [0] | 6 |
| 4 | 合同会社山田水産 | 1162 | [87] | [608] | [[1110, 2910], [24285, 26085]] | [140.36806495,35.77641112] | 4 | [0] | 9 |
Job (id:int, location:Optional[Sequence[float]]=None, location_index:Optional[int]=None, setup:Optional[int]=0, service:Optional[int]=0, delivery:Optional[Sequence[int]]=[0], pickup:Optional[Sequence[int]]=[0], skills:Optional[Set[int]]=None, priority:Optional[int]=0, time_windows:Optional[Sequence[Tuple[int,int]]]=None, description:Optional[str]='')
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.Entity ()
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.輸送は，運搬車のデポ（出発地点もしくは最終到着地点）以外での荷物の積み込みと積み降ろしを表し，以下の列から構成される．
| amount | pickup_point | pickup_service | pickup_time_windows | pickup_location | pickup_index | delivery_point | delivery_service | delivery_time_windows | delivery_location | delivery_index | skills | priority | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | [38] | 有限会社吉田食品 | 835 | [[7935, 9735], [18905, 20705]] | [139.8874225,35.06991256] | 5 | 有限会社青山鉱業 | 672 | [[10863, 12663], [33913, 35713]] | [139.92525888,35.84571653] | 6 | [0] | 0 |
Shipment (pickup:__main__.ShipmentStep, delivery:__main__.ShipmentStep, amount:Optional[Sequence[int]]=[0], skills:Optional[Set[int]]=None, priority:Optional[int]=0)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.ShipmentStep (id:int, location:Optional[Tuple[float,float]]=None, location_index:Optional[int]=None, setup:Optional[int]=0, service:Optional[int]=0, time_windows:Optional[Sequence[Tuple[int,int]]]=None, description:Optional[str]='')
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.Break (id:int, time_windows:Optional[Sequence[Tuple[int,int]]]=[], service:Optional[int]=0, description:Optional[str]='', max_load:Optional[Sequence[int]]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.temp = []
for id, row in enumerate(break_df.itertuples()):
#print(ast.literal_eval(row.time_windows))
temp = {"id":id,
"description": row.description,
"time_windows": ast.literal_eval(row.time_windows),
"service": row.service
}
b = Break(**temp)
bBreak(id=1, time_windows=[(32400, 39600)], service=1800, description='supper', max_load=None)運搬車（トラック，車両）は，輸送手段の総称であり， 以下の列をもつ．
Vehicle (id:int, start:Optional[Sequence[float]]=None, end:Optional[Sequence[float]]=None, start_index:Optional[int]=None, end_index:Optional[int]=None, profile:Optional[str]='car', capacity:Optional[Sequence[int]]=None, skills:Optional[Set[int]]=None, time_window:Optional[Tuple[int,int]]=None, breaks:Optional[Sequence[__main__.Break]]=None, description:str='', costs:__main__.VehicleCosts=VehicleCosts(fixed=0, per_hour=3600, per_km=0), speed_factor:Optional[float]=1.0, max_tasks:Optional[int]=None, max_travel_time:Optional[int]=None, steps:Sequence[__main__.VehicleStep]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.VehicleStep (step_type:__main__.VEHICLE_STEP_TYPE, id:Optional[int]=None, service_at:Optional[int]=None, service_after:Optional[int]=None, service_before:Optional[int]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.VEHICLE_STEP_TYPE (START:str='start', END:str='end', BREAK:str='break', SINGLE:str='single', PICKUP:str='pickup', DELIVERY:str='delivery')
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.VehicleCosts (fixed:Optional[int]=0, per_hour:int=3600, per_km:Optional[int]=0)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.vehicle = Vehicle(id=7, start_index=0, end_index=0, time_window=(0,100), costs = VehicleCosts(per_hour=10) )
#eval(repr(vehicle))
print(vehicle.model_dump_json(exclude_none=True)){"id":7,"start_index":0,"end_index":0,"profile":"car","time_window":[0,100],"description":"","costs":{"fixed":0,"per_hour":10,"per_km":0},"speed_factor":1.0}Matrix (durations:List[List]=None, distances:List[List]=None, costs:List[List]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.配送計画モデルを表すクラス
Model (jobs:Optional[Sequence[__main__.Job]]=None, shipments:Optional[Sequence[__main__.Shipment]]=None, vehicles:Optional[Sequence[__main__.Vehicle]]=None, matrices:Optional[Dict[str,__main__.Matrix]]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.break0 =Break(id=0, time_windows = [(1000,2000)], service = 100, max_load=[20])
model = Model()
model.vehicles= [Vehicle(id=7, start_index=0, end_index=0, capacity=[100], time_window=[0,20000],
costs = VehicleCosts(fixed=99999), breaks=[break0]),
Vehicle(id=8, start_index=2, end_index=2, capacity=[100],breaks=[break0])]
model.jobs = [ Job(id=1, location_index=0, delivery=[10], pickup=[30], time_windows=[(0,100),(300,10000)]),
Job(id=12, location_index=1, delivery=[20]),
Job(id=1616, location_index=2, delivery=[30]),
Job(id=1717, location_index=3, delivery=[40])]
model.matrices = {"car": Matrix(
durations= [[0, 2104, 197, 1299],
[2103, 0, 2255, 3152],
[197, 2256, 0, 1102],
[1299, 3153, 1102, 0]]
)
}
model.shipments=[Shipment(pickup=ShipmentStep(id=1, location_index=2),
delivery=ShipmentStep(id=124, location_index=3, time_windows=[ (500,2000) ]),
amount=[10])]
model.model_dump_json(exclude_none=True)'{"jobs":[{"id":1,"location_index":0,"setup":0,"service":0,"delivery":[10],"pickup":[30],"priority":0,"time_windows":[[0,100],[300,10000]],"description":""},{"id":12,"location_index":1,"setup":0,"service":0,"delivery":[20],"pickup":[0],"priority":0,"description":""},{"id":1616,"location_index":2,"setup":0,"service":0,"delivery":[30],"pickup":[0],"priority":0,"description":""},{"id":1717,"location_index":3,"setup":0,"service":0,"delivery":[40],"pickup":[0],"priority":0,"description":""}],"shipments":[{"pickup":{"id":1,"location_index":2,"setup":0,"service":0,"description":""},"delivery":{"id":124,"location_index":3,"setup":0,"service":0,"time_windows":[[500,2000]],"description":""},"amount":[10],"priority":0}],"vehicles":[{"id":7,"start_index":0,"end_index":0,"profile":"car","capacity":[100],"time_window":[0,20000],"breaks":[{"id":0,"time_windows":[[1000,2000]],"service":100,"description":"","max_load":[20]}],"description":"","costs":{"fixed":99999,"per_hour":3600,"per_km":0},"speed_factor":1.0},{"id":8,"start_index":2,"end_index":2,"profile":"car","capacity":[100],"breaks":[{"id":0,"time_windows":[[1000,2000]],"service":100,"description":"","max_load":[20]}],"description":"","costs":{"fixed":0,"per_hour":3600,"per_km":0},"speed_factor":1.0}],"matrices":{"car":{"durations":[[0,2104,197,1299],[2103,0,2255,3152],[197,2256,0,1102],[1299,3153,1102,0]]}}}'引数： - model: 最適化モデルを入れた辞書 - matrix = False: 移動時間データを用いる場合True - thread: 最適化に使用するスレッド数 - explore: 探索の度合いを表すパラメータ； 0から5の整数で，大きいほど念入りに探索する． - cloud: 複数人が同時実行する可能性があるときTrue（既定値はFalse）; Trueのとき，ソルバー呼び出し時に生成されるファイルにタイムスタンプを追加し，計算終了後にファイルを消去する． - osrm: OSRMを外部のサーバーで呼び出しをしたいときTrue， localhostで呼び出すときFalse
返値： - input_dic: データ入力のためのJSONデータ - output_dic: 結果出力のためのJSONデータ - error: エラーメッセージを入れた文字列
optimize_vrp (model, matrix=False, threads=4, explore=5, cloud=False, osrm=False, host='localhost')
Solution (code:int, error:Optional[str]=None, summary:Optional[__main__.Summary]=None, unassigned:Optional[Sequence[Any]]=None, routes:Optional[Sequence[__main__.Route]]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.Route (vehicle:int, steps:Optional[Sequence[Any]], cost:int, setup:int, service:int, duration:int, waiting_time:int, priority:int, violations:Optional[Sequence[__main__.Violation]]=None, delivery:Optional[Sequence[int]]=None, pickup:Optional[Sequence[int]]=None, description:str=None, geometry:Optional[str]=None, distance:Optional[int]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.Violation (cause:str, duration:Optional[int]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.Summary (cost:int, routes:int, unassigned:int, setup:int, service:int, duration:int, waiting_time:int, priority:int, violations:Optional[Sequence[str]], delivery:Optional[Sequence[int]], pickup:Optional[Sequence[int]], distance:Optional[int]=None)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.引数：
返値：
summary_df: 解の概要のデータフレーム
route_summary_df: ルートの概要のデータフレーム
unassigned_df: 未割り当てのジョブ・輸送のデータフレーム
route_df_dic: キーをルート番号とし，ルートの情報を格納したデータフレームを値とした辞書． ルートデータフレームの列は以下の通り．
make_solution (output_dic:dict)
地図アプリ OSRM を用いて移動時間と移動距離を計算する．
引数： - node_df: ノードデータフレーム（緯度経度情報を含む） - toll: 有料道路が使用可のときTrue（既定値 True) - host: ホスト名；既定値は “localhost”
返値： - durations: 地点間の移動時間の配列 - distances: 地点間の距離の配列
compute_distance_table_for_vrp (node_df, toll=True, host='localhost')
移動時間と移動距離を計算し，移動時間の度数分布表を描画する．
node_df = pd.read_csv(folder +"node.csv")
durations, distances = compute_distance_table_for_vrp(node_df, toll=False, host=host)
node_df.head()| Unnamed: 0 | name | zip | 都道府県 | 市区町村 | 大字 | location | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 合同会社藤本建設 | 2860114 | 千葉県 | 成田市 | 本城 | [140.37645821,35.73859296] |
| 1 | 1 | 有限会社西之園運輸 | 2850053 | 千葉県 | 佐倉市 | 下勝田 | [140.26801893,35.69354415] |
| 2 | 2 | 株式会社村山印刷 | 2620021 | 千葉県 | 千葉市花見川区 | 花園町 | [140.07757664,35.654959999999996] |
| 3 | 3 | 青田印刷合同会社 | 2991902 | 千葉県 | 安房郡鋸南町 | 保田 | [139.85405777,35.14919189] |
| 4 | 4 | 合同会社山田水産 | 2820021 | 千葉県 | 成田市 | 駒井野（成田国際空港内） | [140.36806495,35.77641112] |
引数： - node_df: 点のデータフレーム
返値： - time_df: 発地，着地，移動時間（秒），道路距離（m）,高速なしの移動時間（秒），高速なしの道路距離（m)を入れたデータフレーム
def make_time_df_for_vrp(node_df, host="localhost"):
MAX_ = 100000
try:
node_df.reset_index(inplace=True)
except:
pass
durations, distances = compute_distance_table_for_vrp(node_df, toll=True, host=host) #高速利用
durations2, distances2 = compute_distance_table_for_vrp(node_df, toll=False, host=host) #高速利用なし
n = len(durations)
name_dic = node_df.name.to_dict() #番号を顧客名に写像
from_id, to_id, duration, distance, duration2, distance2 =[],[],[],[],[],[]
from_name, to_name = [], []
for i in range(n):
for j in range(n):
if durations[i][j] is not None and durations2[i][j] is not None:
from_id.append(i)
to_id.append(j)
from_name.append(name_dic[i])
to_name.append(name_dic[j])
duration.append( int(durations[i][j]) )
distance.append( int(distances[i][j]) )
duration2.append( int(durations2[i][j]) )
distance2.append( int(distances2[i][j]) )
else:
#距離・時間がない場合
from_id.append(i)
to_id.append(j)
from_name.append(name_dic[i])
to_name.append(name_dic[j])
duration.append( MAX_ )
distance.append( MAX_ )
duration2.append( MAX_ )
distance2.append( MAX_ )
time_df = pd.DataFrame({"from_node": from_id, "from_name": from_name, "to_node":to_id,
"to_name":to_name, "time": duration, "distance": distance,
"time(no toll)": duration2, "distance(no toll)": distance2 })
return time_dfnode_df = pd.read_csv(folder +"node10.csv")
time_df = make_time_df_for_vrp(node_df, host)
time_df.head()| from_node | from_name | to_node | to_name | time | distance | time(no toll) | distance(no toll) | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 合同会社前田建設 第 18 支店 | 0 | 合同会社前田建設 第 18 支店 | 0 | 0 | 0 | 0 |
| 1 | 0 | 合同会社前田建設 第 18 支店 | 1 | 有限会社阿部運輸 第 73 支店 | 18927 | 409022 | 22105 | 465388 |
| 2 | 0 | 合同会社前田建設 第 18 支店 | 2 | 株式会社村上印刷 第 98 支店 | 10696 | 246981 | 10696 | 246981 |
| 3 | 0 | 合同会社前田建設 第 18 支店 | 3 | 佐藤印刷合同会社 第 9 支店 | 23557 | 527974 | 26465 | 584830 |
| 4 | 0 | 合同会社前田建設 第 18 支店 | 4 | 合同会社青木水産 第 33 支店 | 20808 | 474615 | 23726 | 521476 |
引数： - n: 地点数 - random_seed=1：乱数の種 - prefecture=None: 県名 - matrix: 移動時間行列を生成するとき True
返値： - node_df: 顧客データフレーム - time_df: 移動時間データフレーム（matrix引数がTrueのとき；それ以外のときは，空の文字列”“を返す．）
generate_node (n, random_seed=1, prefecture=None, matrix=False, host='test-osrm-intel.aq-cloud.com')
郵便番号データをもとに日本のノードデータをランダムに生成する関数
# 日本の郵便番号データは分割して保存されているものを内部で読み込む
node_df, time_df = generate_node(n=30, random_seed=1, prefecture="千葉県", matrix=True, host=host)
node_df.head()| name | zip | 都道府県 | 市区町村 | 大字 | location | |
|---|---|---|---|---|---|---|
| 0 | 合同会社近藤保険 第 18 支店 | 2860121 | 千葉県 | 成田市 | 駒井野（その他） | [140.37146572,35.77489448] |
| 1 | 有限会社鈴木保険 第 73 支店 | 2617102 | 千葉県 | 千葉市美浜区 | 中瀬ワールドビジネスガーデン（２階） | [140.0390776,35.64860739] |
| 2 | 山田電気株式会社 第 98 支店 | 2870236 | 千葉県 | 成田市 | 津富浦 | [140.40760995,35.83235231] |
| 3 | 有限会社佐藤電気 第 9 支店 | 2780016 | 千葉県 | 野田市 | 二ツ塚 | [139.91482316,35.93875527] |
| 4 | 斎藤保険株式会社 第 33 支店 | 2893184 | 千葉県 | 匝瑳市 | 栢田 | [140.55222906,35.64056327] |
| from_node | from_name | to_node | to_name | time | distance | time(no toll) | distance(no toll) | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 合同会社近藤保険 第 18 支店 | 0 | 合同会社近藤保険 第 18 支店 | 0 | 0 | 0 | 0 |
| 1 | 0 | 合同会社近藤保険 第 18 支店 | 1 | 有限会社鈴木保険 第 73 支店 | 1889 | 39918 | 2306 | 45381 |
| 2 | 0 | 合同会社近藤保険 第 18 支店 | 2 | 山田電気株式会社 第 98 支店 | 642 | 9559 | 642 | 9559 |
| 3 | 0 | 合同会社近藤保険 第 18 支店 | 3 | 有限会社佐藤電気 第 9 支店 | 2860 | 56103 | 2860 | 56103 |
| 4 | 0 | 合同会社近藤保険 第 18 支店 | 4 | 斎藤保険株式会社 第 33 支店 | 1634 | 26391 | 1634 | 26391 |
引数： - n: 地点数 - lat_center: 中心緯度 - lon_center: 中心経度 - std: 正規分布の標準偏差 - country_code: 国を表すコード（名称をランダムに生成するときに用いる．） 既定値は日本 ja_JP． その他の国コードについては https://faker.readthedocs.io/en/master/locales.html 参照． - random_seed=1：乱数の種 - matrix: 移動時間行列を生成するとき True
返値： - node_df: 顧客データフレーム - time_df: 移動時間データフレーム（matrix引数がTrueのとき；それ以外のときは，空の文字列”“を返す．）
generate_node_normal (n, lat_center, lon_center, std=0.1, country_code='ja_JP', random_seed=1, matrix=False)
ノードデータを正規分布にしたがってランダムに生成する関数
lat_center = 30.567201
lon_center = 120.112051
std = 0.1
country_code = 'zh_CN' #中国
random_seed = 1
node_df, time_df = generate_node_normal(n=10, lat_center=lat_center, lon_center=lon_center, std= std, country_code=country_code, random_seed=1, matrix=False)
node_df.head()| name | location | |
|---|---|---|
| 0 | 昊嘉科技有限公司 | [120.25826179370449,30.729635536366324] |
| 1 | 菊风公司传媒有限公司 | [119.90603692905023,30.506025358634993] |
| 2 | 佳禾传媒有限公司 | [120.07980927959865,30.514383824773656] |
| 3 | 晖来计算机传媒有限公司 | [120.07364556453315,30.459904137784385] |
| 4 | 新宇龙信息传媒有限公司 | [120.22542794423354,30.65374176293247] |
データフレームからモデルを生成する関数．
引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム - time_df: 移動時間データフレーム（既定値は「なし」を表すNone）
返値： - model: METROモデルのインスタンス
build_model_for_vrp (job_df, shipment_df, vehicle_df, break_df, time_df=None, cost_per_hour=3600)
# no = "01"
# job_df = pd.read_csv(folder+"job"+no+".csv", index_col=0)
# shipment_df = pd.read_csv(folder+"shipment"+no+".csv", index_col=0)
# vehicle_df = pd.read_csv(folder+"vehicle"+no+".csv", index_col=0)
# time_df = pd.read_csv(folder+"time"+no+".csv", index_col=0)
# break_df = pd.read_csv(folder +"break.csv", index_col=0)
# model = build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df, time_df, cost_per_hour=1)
# pprint(model.jobs[0])配送計画のランダムな問題例を生成する関数
引数： - node_df: ノードデータフレーム - num_depots = 1: デポ数 - open_flag = False: Trueだと，運搬車の最終地点がデポでなく，最後の訪問地点となる． - num_jobs=10: ジョブ数 - num_shipments=0: デポ以外での積み込み積み降ろしの輸送数 - num_time_windows =1: 時間枠の数 - time_window_bounds =(0,36000): 時間枠の下限と上限の組 - time_window_ratio = 0.9: 稼働時間に対する時間枠の比（小さいほど時間枠が狭くなる） - delivery_bounds = (0,0): 配達量の下限と上限の組 - pickup_bounds = (0,0): 集荷量の下限と上限の組 - service_bounds= (0,0): 作業時間の下限と上限の組 - amount_bounds = (0,0): デポ以外での積み込み積み下ろし量の下限と上限の組 - priority_bounds = (0,100): 優先度の下限と上限の組；0..100の間にする必要がある． 優先度は訪問しない場合のペナルティ量を表す（大きいほどルートに含まれる）． - load_factor = 0.9: 運搬車の積載率の目標値 - num_customers_per_route = 5： １ルートあたりの配達件数 - skill_flag = False: スキルを考慮した問題例とするときTrue - breaks = None: 休憩の番号のリスト．既定値は「なし」を表す None． 例における休憩データの場合で，昼食だけの場合は[0]，昼食と夕食の場合は[0,1]と設定する．
返値： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム
generate_vrp (node_df, num_depots=1, open_flag=False, num_jobs=10, num_shipments=0, num_time_windows=1, time_window_bounds=(0, 36000), time_window_ratio=0.9, delivery_bounds=(0, 0), pickup_bounds=(0, 0), service_bounds=(0, 0), amount_bounds=(0, 0), priority_bounds=(0, 100), load_factor=0.9, num_customers_per_route=5, skill_flag=False, breaks=None)
郵便番号データをもとに配送計画問題のデータをランダムに生成する関数（ノード生成を分離）
メモリは問題ないが，オーバーフローに注意する必要がある．
#パラメータの準備
matrix = True
delivery_bounds = 100, 1000
pickup_bounds = 50, 100
service_bounds = 10*60, 20*60 #seconds
amount_bounds = 1,100
priority_bounds = 0,100
load_factor = 0.8 #積載率
num_customers_per_route = 3 #1ルートに含まれる顧客数
num_time_windows = 1 #時間枠の数
time_window_ratio =0.5 #時間枠の幅を決めるパラメータ
num_depots = 1
num_jobs = 30 #00
num_shipments = 0
n= num_depots + num_jobs + num_shipments*2
#日本のノードデータ生成
node_df, time_df = generate_node(n=n, random_seed=2, prefecture="埼玉県", matrix=matrix, host=host)
#中国のデータ生成
# lat_center = 30.567201
# lon_center = 120.112051
# std = 0.1
# country_code = 'zh_CN'
# random_seed = 1
# node_df, time_df = generate_node_normal(n=n, lat_center=lat_center, lon_center=lon_center, std= std, country_code=country_code, random_seed=1, matrix=matrix)
job_df, shipment_df, vehicle_df = generate_vrp(node_df, num_depots=num_depots, open_flag=False,
num_jobs=num_jobs, num_shipments = num_shipments,
num_time_windows = num_time_windows,
time_window_bounds =(0,36000), time_window_ratio = time_window_ratio,
delivery_bounds= delivery_bounds, pickup_bounds=pickup_bounds, service_bounds = service_bounds, amount_bounds=amount_bounds,
priority_bounds =priority_bounds, load_factor=load_factor, num_customers_per_route=num_customers_per_route, skill_flag=False, breaks=[0])model = build_model_for_vrp(job_df, shipment_df, vehicle_df, None, time_df, cost_per_hour=3600)
input_dic, output_dic, error = optimize_vrp(model, matrix=True, explore=1, cloud=False, osrm=True, host=host)
output_file = open(f'output1.json', 'r')
output_dic = json.load(output_file)
summary_df, route_summary_df, unassigned_df, route_df_dic = make_solution(output_dic)
summary_df
#route_summary_dfNow solving ...
Done
CPU times: user 39.3 ms, sys: 8.69 ms, total: 48 ms
Wall time: 478 ms| cost | routes | unassigned | setup | service | duration | waiting_time | priority | violations | delivery | pickup | distance | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 57227 | 10 | 0 | 0 | 27611 | 57227 | 0 | 1800 | [] | [16684] | [2299] | None |
他の最適化アルゴリズムも準備しておく．問題によって，使い分ける．
GA Hybrid ：
列生成： CPソルバーやビームサーチで列生成をしてMIPソルバーで主問題を解く．
制約がきつい場合には，列生成法が有効になるケースがある． 特に，航空機や船などのスケジューリング問題は， 疎なグラフになるので，列生成が高速にできる可能性がある．
主問題は混合整数最適化ソルバーで集合分割（被覆）問題を解き， 列生成子問題は，以下の2通りの解法を考える．
引数
SolutionPrinter (variables:Dict, G:networkx.classes.digraph.DiGraph, prize:List, start_index:int, limit:int)
得られた巡回路とその費用を保管する
pricing (dual:List, start_index:int, capacity:Optional[int], max_duration:Optional[int], G:networkx.classes.digraph.DiGraph, limit:int=100)
引数
pricing_bs (dual, start_index, capacity, max_duration, G, limit=1000, search_width=20)
BeamNode (path_list:List[int]=[], departure:int=0, duration:int=0, total_cost:int=0, residual:int, min_residual:int)
Usage docs: https://docs.pydantic.dev/2.6/concepts/models/
A base class for creating Pydantic models.
Attributes: class_vars: The names of classvars defined on the model. private_attributes: Metadata about the private attributes of the model. signature: The signature for instantiating the model.
__pydantic_complete__: Whether model building is completed, or if there are still undefined fields.
__pydantic_core_schema__: The pydantic-core schema used to build the SchemaValidator and SchemaSerializer.
__pydantic_custom_init__: Whether the model has a custom `__init__` function.
__pydantic_decorators__: Metadata containing the decorators defined on the model.
This replaces `Model.__validators__` and `Model.__root_validators__` from Pydantic V1.
__pydantic_generic_metadata__: Metadata for generic models; contains data used for a similar purpose to
__args__, __origin__, __parameters__ in typing-module generics. May eventually be replaced by these.
__pydantic_parent_namespace__: Parent namespace of the model, used for automatic rebuilding of models.
__pydantic_post_init__: The name of the post-init method for the model, if defined.
__pydantic_root_model__: Whether the model is a `RootModel`.
__pydantic_serializer__: The pydantic-core SchemaSerializer used to dump instances of the model.
__pydantic_validator__: The pydantic-core SchemaValidator used to validate instances of the model.
__pydantic_extra__: An instance attribute with the values of extra fields from validation when
`model_config['extra'] == 'allow'`.
__pydantic_fields_set__: An instance attribute with the names of fields explicitly set.
__pydantic_private__: Instance attribute with the values of private attributes set on the model instance.デポ以外での積み込み積み降ろしがなく， 荷の次元が1の問題はGAソルバーに変換して解くことができる．
GAソルバーはメモリを多く必要とするが，解の質は上がる（さらに，計算時間を自由に設定できる）．
| 問題サイズ | 計算時間(s) | メモリ |
|---|---|---|
| 5000 | 240 | 5GB |
| 8000 | 1440 | 10.5GB |
引数： - sec: 秒数 - start: 開始時刻を表す文字列（年，月，日，時間，分，秒で，“2000-01-01 00:00:00”のような形式で入力する．）
返値： - 開始時刻startからsec秒経過した時刻
time_convert (sec, start)
時間変換のユーテリティ関数
ルート情報をもとにガントチャートを生成する関数
引数： - route_df_dic: キーをルート番号とし，ルートの情報を格納したデータフレームを値とした辞書 - start: 開始時刻を表す文字列（年，月，日，時間，分，秒で，“2000-01-01 00:00:00”のような形式で入力する．）
返値： - fig: plotlyの図オブジェク
gannt_for_vrp (route_df_dic, start='2000/01/01 00:00:00')
ルートのガントチャートを生成する関数
引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - start: 開始時刻を表す文字列（年，月，日，時間，分，秒で，“2000-01-01 00:00:00”のような形式で入力する．）
返値： - fig: plotlyの図オブジェクト
make_tw_fig_for_vrp (job_df, shipment_df, start='2000/01/01 00:00:00')
時間枠を可視化する関数
引数： - output_dic: 最適化の出力を保管した辞書 - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している．
返値： - data: ルートの図オブジェクトのリスト
add_route_for_vrp (output_dic, map_style=0)
引数： - output_dic: 最適化の出力を保管した辞書 - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している．
返値： - data: ルート（通過道路）の図オブジェクトのリスト
add_road_for_vrp (output_dic, map_style=0)
引数： - input_dic: 最適化への入力情報を保管した辞書 - output_dic: 最適化の出力を保管した辞書 - show_mode: 描画モードを表す文字列． ノードのみを表示させるとき “node”， ルートを直線で表示させるとき “route”， 道路情報を図に入れるとき “road” とする． - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している．
返値： - fig: plotlyの地図オブジェクト
make_fig_for_vrp (input_dic, output_dic, show_mode='road', map_style=0)
図の表示
引数： - output_dic: 最適化の出力を保管した辞書 - route_df_dic: ルートのデータフレームを保持する辞書 - route_id: 表示したいルートの番号 - matrix: 移動時間行列を与えるときTrue（既定値はFalse） - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している． - straight: Uターンを抑制するためのフラグ；Trueのとき直線を優先する．FalseのときはUターンを許す．既定値は Noneで，Uターンと移動時間の兼ね合いを考えて自動選択する． - host: ホスト名；既定値は “localhost”
返値： - fig: plotlyの地図オブジェクト
make_detailed_route (input_dic, output_dic, route_df_dic, route_id=0, matrix=False, map_style=0, straight=None, host='localhost')
詳細ルートの図を描画する関数
#問題例読み込み
matrix = True #時間行列を用いる場合 True
map_style = 1
no = "01"
node_df = pd.read_csv(folder+"node"+no+".csv", index_col=0)
job_df = pd.read_csv(folder+"job"+no+".csv", index_col=0)
shipment_df = pd.read_csv(folder+"shipment"+no+".csv", index_col=0)
vehicle_df = pd.read_csv(folder+"vehicle"+no+".csv", index_col=0)
time_df = pd.read_csv(folder+"time"+no+".csv", index_col=0)
break_df = pd.read_csv(folder + "break.csv", index_col=0)
#モデル生成
if matrix:
model = build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df, time_df)
else:
model = build_model_for_vrp(job_df, shipment_df,vehicle_df, break_df)
#new_model = Model(**model)
#if matrix:
# model.matrices ={"car": Matrix(durations = model.matrix) }
#最適化
input_dic, output_dic, error = optimize_vrp(model, matrix=matrix, explore=5, cloud=False, osrm=True, host=host)
if error != "":
print(error)
else:
pass
# if matrix:
# fig = make_fig_for_vrp(input_dic, output_dic, show_mode="route", map_style=map_style)
# else:
# fig = make_fig_for_vrp(input_dic, output_dic, show_mode="road", map_style=map_style)
# plotly.offline.plot(fig);
# route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df,
# vehicle_df, break_df, output_dic)
summary_df, route_summary_df, unassigned_df, route_df_dic = make_solution(output_dic)
# fig = gannt_for_vrp(route_df_dic, start= "2020/01/01 8:00" )
# plotly.offline.plot(fig);
# fig = make_tw_fig_for_vrp(job_df, shipment_df, start= "2020/01/01 8:00")
# plotly.offline.plot(fig);
print("cost=", output_dic["summary"]["cost"])Webシステムで現在使用している例題を以下に示す（Webシステムで番号を選択すると例題がロードされる）．
make_job_excel (wb, n_job=100, num_dim=3, num_tw=3, num_skill=3, date_flag=True)
make_shipment_excel (wb, n_shipment=100, num_dim=3, num_tw=3, num_skill=3, date_flag=True)
make_vehicle_excel (wb, n_vehicle=100, num_dim=3, num_skill=3, num_break=2, date_flag=True)
make_break_excel (wb, num_break=2, date_flag=False)
引数： - n_job: ジョブ数； 既定値は \(100\) - n_shipment: 輸送数； 既定値は \(100\) - n_vehicle: 運搬車数； 既定値は \(100\) - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\) - num_skill: スキル数; 既定値は \(1\) - num_break: 休憩数; 既定値は \(1\) - date_flag: 時間入力を日付時刻型にする場合 True（既定値）， 時刻型にする場合 False（既定値はFalse)
返値：
create_excel_for_metro (n_job=100, n_shipment=100, n_vehicle=100, num_dim=1, num_tw=1, num_skill=1, num_break=1, date_flag=False)
引数 - wb: Excel Workbook
返値： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム
read_dfs_from_excel (wb)
引数 - wb: Excel Workbook
返値： - time_df: 移動時間データフレーム
read_time_from_excel (wb)
移動時間の可視化でも用いる．
compute_table_sub (job_df, shipment_df, vehicle_df, break_df, num_dim=1, num_tw=1, num_skill=1, num_break=1, toll=True, host='localhost')
ジョブ，輸送，運搬車の経度・緯度情報をもとに，地点データを抽出し，ユニークなインデックスをもつ地点シートを追加する．
地点間の移動時間をOSRMで計算し， 移動時間データを生成し，移動時間シートに追加する．
さらに，ジョブ，輸送，運搬車に，対応する地点のインデックス情報を追加する．
引数 - wb: ExcelのWorkBook - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\) - num_skill: スキル数; 既定値は \(1\) - num_break: 休憩数; 既定値は \(1\) - toll: 高速道路を使う場合 True（既定値）
返値 - wb: データを更新したExcelのWorkBook - durations: 移動時間行列（単位は秒） - distances: 距離行列（単位はm）
make_table_for_metro (wb, num_dim=1, num_tw=1, num_skill=1, num_break=1, toll=True, host='localhost')
# num_dim = 2
# num_tw = 2
# num_skill = 2
# num_break=1
# wb = load_workbook("metro-ex1.xlsx")
# job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
# wb, durations, distances = make_table_for_metro(wb, num_dim, num_tw, num_skill, num_break, toll=False, host=host)
# wb.save("metro-ex1-tbl.xlsx")make_time_fig_for_excel (job_df, shipment_df, vehicle_df, break_df, num_dim=1, num_tw=1, num_skill=1, num_break=1, toll=True, host='localhost')
# num_dim = 2
# num_tw = 2
# num_skill = 2
# num_break=1
# toll = False
# wb = load_workbook("metro-ex1.xlsx")
# # num_dim = 2
# # num_tw = 1
# # num_skill = 8
# # num_break=1
# # toll = False
# # wb = load_workbook("metro3.xlsx")
# job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
# fig, fig_hist = make_time_fig_for_excel(job_df, shipment_df, vehicle_df, break_df, num_dim,
# num_tw, num_skill, num_break, toll, host=host)
# plotly.offline.plot(fig);
# #plotly.offline.plot(fig_hist);引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\)
返値： - fig: Plotlyの図オブジェクト
make_tw_fig_for_excel (job_df, shipment_df, vehicle_df, num_dim=1, num_tw=1)
Excel用のデータフレームを用いた時間枠を可視化する関数
ジョブの荷量が運搬車の積載量上限でまかなえるかを，線形最適化を用いて簡易的に分析することを考える．
荷量は複数の属性をもつ場合があるので，多次元のベクトルとして扱う．その次元数と積み込み・積み降ろしの区別をするので，全体で「次元数$$2」の資源制約をもつと考える．
次元の添字を \(j\)，積み込み・積み降ろしの添字を \(k (=0,1)\) とし， \(j,k\) の組を資源とよぶ．
ジョブ（顧客）を運搬車に割り当てる際には，スキルを考慮する必要がある．顧客のスキル集合が運搬車のスキル集合の部分集合になっている場合に割り当て可能になる．
以下のパラメータと変数を導入する．
パラメータ - \(d_{ijk}\): 顧客 \(i\) の資源 \(j,k\) の荷量 - \(C_{vj}\): 運搬車 \(v\) の次元 \(j\) の積載量上限 - \(M\): 大きな数（超過ペナルティを優先するために用いる．） - \(\epsilon\): 小さな数（不用意な超過・余裕量を \(0\) にするため．）
変数 - \(x_{iv}\): 顧客 \(i\) を運搬車 \(v\) に割り当てる割合； 顧客 \(i\) のスキルが運搬車 \(v\) のスキル集合の部分集合になっているときだけ定義する． - \(surplus_{vjk}\): 運搬車 \(v\) の資源 \(j,k\) の超過量の割合 - \(slack_{vjk}\): 運搬車 \(v\) の資源 \(j,k\) の余裕量の割合 - \(y\): 最大の超過割合 - \(z\): 最小の割合
定式化 \[ \begin{array}{lll} minimize & My-z +\epsilon \sum_{v,j,k} (surplus_{vjk}+slack_{vjk}) & \\ s.t. & \sum_{v} x_{iv} = 1 & \forall i \\ & \sum_{i} d_{ijk} x_{iv} = C_{vj}(1- slack_{vjk} +surplus_{vjk}) & \forall v,j,k \\ & 0 \leq slack_{vjk} \leq z & \forall v,j,k \\ & 0 \leq surplus_{vjk} \leq y & \forall v,j,k \\ & x_{iv} \geq 0 & \forall i,v \end{array} \]
引数： - job_df: ジョブデータフレーム - vehicle_df: 運搬車データフレーム - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\) - num_skill: スキル数; 既定値は \(1\)
返値： - fig_surplus: 超過のPlotly図オブジェクト - fig_slack: 不足量のPlotly図オブジェクト
analyze_load (job_df, vehicle_df, num_dim=1, num_tw=1, num_skill=1)
# #wb = load_workbook("metro-ex6.xlsx")
# wb = load_workbook("metro-ex1.xlsx")
# job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
# fig_surplus, fig_slack = analyze_load(job_df, vehicle_df, num_dim=2, num_tw = 2, num_skill = 1)
#plotly.offline.plot(fig_slack);
#plotly.offline.plot(fig_surplus);show_load (job_df, num_dim=1, num_tw=1)
引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム - num_dim: 積載重量の次元数; 既定値は \(3\) - num_tw: 時間枠の数; 既定値は \(3\) - num_skill: スキル数; 既定値は \(3\) - num_break: 休憩数; 既定値は \(3\) - date_flag: 時間入力を日付時刻型にする場合 True（既定値）， 時刻型にする場合 False （未使用）
返値： - job_df: （最適化用の）ジョブデータフレーム - shipment_df: （最適化用の）輸送データフレーム - vehicle_df: （最適化用の）運搬車データフレーム - break_df: （最適化用の）休憩データフレーム - start: 運搬車の最早開始時刻
create_dfs_from_excel (job_df, shipment_df, vehicle_df, break_df, num_dim=1, num_tw=1, num_skill=1, num_break=1, date_flag=False)
# num_dim = 2
# num_tw = 2
# num_skill = 2
# num_break=1
# wb = load_workbook("metro-ex1.xlsx")
# num_dim = 1
# num_tw = 1
# num_skill = 1
# num_break=1
# wb = load_workbook("metro-ex3.xlsx")
#wb = load_workbook("metro_example1.xlsx")
#wb = load_workbook("metro-ex1-tbl.xlsx")
#wb, durations, distances = make_table_for_metro(wb, num_dim, num_tw, num_skill, num_break, toll=True, host=host)
# job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
# job_df, shipment_df, vehicle_df, break_df, start = create_dfs_from_excel(job_df, shipment_df, vehicle_df, break_df,
# num_dim, num_tw, num_skill, num_break, date_flag = False)#time_df = read_time_from_excel(wb)
#model = build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df, time_df)
# model = build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df)
# input_dic, output_dic, error = optimize_vrp(model, matrix=False, explore=5, cloud=False, osrm=True, host=host)
# route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)
# route_df_dic[0]引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - output_dic: 最適化の出力を保管した辞書
返値： - unassigned_job_df: 未割り当てのジョブデータフレーム - unassigned_shipment_df: 未割り当ての輸送データフレーム - unassigned_vehicle_df : 未割り当ての運搬車データフレーム
unassigned_for_excel (job_df, shipment_df, vehicle_df, output_dic)
Excel用の未割り当てを返す関数
# #
# wb = load_workbook("metro-ex1.xlsx")
# #wb = load_workbook("metro-ex5.xlsx")
# job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
# job_df0 = job_df.copy()
# shipment_df0 = shipment_df.copy()
# vehicle_df0 = vehicle_df.copy()
# job_df, shipment_df, vehicle_df, break_df, start = create_dfs_from_excel(job_df, shipment_df, vehicle_df, break_df,
# num_dim = 2, num_tw = 2, num_skill = 2, num_break=1, date_flag = False)
# model = build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df)
# input_dic, output_dic, error = optimize_vrp(model, matrix=False, explore=5, cloud=False)
# route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)
# unassigned_job_df, unassigned_shipment_df, unassigned_vehicle_df = unassigned_for_excel(job_df0, shipment_df0, vehicle_df0, output_dic)
# unassigned_vehicle_df引数： - start: 運搬車の最早開始時刻 - output_dic: 最適化で出力されたJSONデータ - unassigned_job_df: 未割り当てのジョブのデータフレーム - unassigned_shipment_df: 未割り当ての輸送のデータフレーム - output_dic: 最適化出力のJSONnum_tw
返値： - wb: 結果を書き込んだExcel Worksheet
write_result_excel (start, route_df_dic, unassigned_job_df, unassigned_shipment_df, unassigned_vehicle_df, output_dic, num_tw)