Highway Passenger Transport based Express Parcel Service (HPTB-EPS) is an emerging business which uses unutilised room of coach trunk to ship parcels between major cities. While it is reaping more and more express market, the managers are facing difficult decisions to design the service network. This paper investigates the HPTB-EPS network design problem and analyses the time-space characteristics of such network. A mixed-integer programming model is formulated integrating the service decision, frequency and network flow distribution. To solve the model, a decomposition-based heuristic algorithm is designed by decomposing the problem as three steps: construction of service network, service path selection and distribution of network flow. Numerical experiment using real data from our partner company shows that our model and algorithm are effective and better than the current decision rule. The sensitivity analysis demonstrates the robustness and flexibility of the solutions of the model.